Publication

Constant Factor Approximation for ATSP with Two Edge Weights

Publications associées (42)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

A PTAS for the Highway Problem

Thomas Rothvoss

In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the assoc ...

2011

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

Connected facility location via random facility sampling and core detouring

Friedrich Eisenbrand, Thomas Rothvoss

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...

2010

Linear Compressive Networks

Michael Christoph Gastpar, Naveen Goela

A linear compressive network (LCN) is defined as a graph of sensors in which each encoding sensor compresses incoming jointly Gaussian random signals and transmits (potentially) low-dimensional linear projections to neighbors over a noisy uncoded channel. ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

Temporally Consistent Layer Depth Ordering Via Pixel Voting For Pseudo 3D Representation

Engin Türetken

A new region-based depth ordering algorithm is proposed based on the segmented motion layers with affine motion models. Starting from an initial set of layers that are independently extracted for each frame of an input sequence, relative depth order of eve ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

On Depth-bounded Message Passing Systems

Damien Zufferey

We explore the border between decidability and undecidability of verification problems related to message passing systems that admit unbounded creation of threads and name mobility. Inspired by use cases in real-life programs we introduce the notion of dep ...

2009

Asymmetric information embedding

Mohammad Amin Shokrollahi

In the Information Embedding Problem one is given a piece of data which can be altered only conditionally, for example only at certain places. One is then asked to embed an arbitrary message into the data by only applying admissible changes to the data. Th ...

Springer-Verlag2008

On Broadcast with a Common Message over Networks

Satish Babu Korada, Dinkar Vasudevan

We consider the following communication problem over a directed graph. A source node wants to transmit a common message to a set of receiver nodes along with a private message to each of the receivers. We show a class of networks for which the achievable r ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2008

Approximating connected facility location problems via Random facility sampling and core detouring

Friedrich Eisenbrand, Thomas Rothvoss

2008

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010