Publication

An Improved LP-based Approximation for Steiner Tree

Publications associées (77)

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

Constrained Binary Identification Problem

Amin Karbasi, Morteza Zadimoghaddam

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the “20 questions game” of information theory and is closely related to lossless so ...

2013

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Association for Computing Machinery2013

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic

Location privacy is a major concern in pervasive networks where static device identifiers enable malicious eavesdroppers to continuously track users and their movements. In order to prevent such identifier-based tracking, devices could coordinate regular i ...

2013

New Results in the Theory of Linear and Integer Programming

Nicolai Hähnle

The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...

EPFL2012

Hardness of Vertex Deletion and Project Scheduling

Ola Nils Anders Svensson

Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer k ≥ 2 and arbitrary small ε > 0, the Feedback Vertex Set problem and the DAG Vertex Deletion problem ...

Springer2012

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Ola Nils Anders Svensson, Klaus Jansen

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objecti ...

Assoc Computing Machinery2012

Primal-dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

Carsten Moldenhauer

NODE-WEIGHTED STEINER FOREST is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider t ...

Academic Press Inc Elsevier Science2011

Complexity of the critical node problem over trees

Marco Di Summa

In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. ...

2011

Minimum clique partition in unit disk graphs

János Pach

The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given n points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting poi ...

Springer Verlag2011

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