64 Search Results for "Devanur, Nikhil R."

Volume

LIPIcs, Volume 28

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain

Editors: Klaus Jansen, José Rolim, Nikhil R. Devanur, and Cristopher Moore

Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014
LIPIcs, Volume 28, APPROX/RANDOM'14, Complete Volume

Authors: Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
LIPIcs, Volume 28, APPROX/RANDOM'14, Complete Volume
Cite as

Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore. LIPIcs, Volume 28, APPROX/RANDOM'14, Complete Volume. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Proceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2014,
  title =	{{LIPIcs, Volume 28, APPROX/RANDOM'14, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014},
  URN =		{urn:nbn:de:0030-drops-47603},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014},
  annote =	{Keywords: Network Architecture and Design, Computer-communication, Coding and Information Theory, Theory of Computation, Computation by Abstract Devices, Models of Computation – relations between models, Modes of Computation, Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Klaus Jansen, José Rolim, Nikhil R. Devanur, and Cristopher Moore

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as

Klaus Jansen, José Rolim, Nikhil R. Devanur, and Cristopher Moore. Frontmatter, Table of Contents, Preface, Conference Organization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. i-xviii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2014.i,
  author =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{i--xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.i},
  URN =		{urn:nbn:de:0030-drops-46846},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.1
Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier

Authors: Ittai Abraham, Shiri Chechik, and Kunal Talwar

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
A fully dynamic approximate distance oracle is a distance reporting data structure that supports dynamic insert edge and delete edge operations. In this paper we break a longstanding barrier in the design of fully dynamic all-pairs approximate distance oracles. All previous results for this model incurred an amortized cost of at least Omega(n) per operation. We present the first construction that provides constant stretch and o(m) amortized update time. For graphs that are not too dense (where |E| = O(|V|^{2-delta}) for some delta>0 we break the O(n) barrier and provide the first construction with constant stretch and o(n) amortized cost.
Cite as

Ittai Abraham, Shiri Chechik, and Kunal Talwar. Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 1-16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.APPROX-RANDOM.2014.1,
  author =	{Abraham, Ittai and Chechik, Shiri and Talwar, Kunal},
  title =	{{Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.1},
  URN =		{urn:nbn:de:0030-drops-46857},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.1},
  annote =	{Keywords: Shortest Paths, Dynamic Algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.17
Approximation Algorithms for Minimum-Load k-Facility Location

Authors: Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, and Chaitanya Swamy

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (MLkFL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k > 0. Assigning client j to a facility f incurs a connection cost d(f, j). The goal is to open a set F' of k facilities, and assign each client j to a facility f(j) in F' so as to minimize maximum, over all facilities in F', of the sum of distances of clients j assigned to F' to F'. We call this sum the load of facility f. This problem was studied under the name of min-max star cover in [6, 2], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, and only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polynomial time approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NP-hard on line metrics. We also devise a quasi-PTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics, and resilient to attack by the variety of techniques that have been successfully applied to facility-location problems. For instance, we show that: (a) even a configuration-style LP-relaxation has a bad integrality gap; and (b) a multi-swap k-median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding the problem, and argue that a MILP-solution minimizing a certain potential function possesses the desired structure, and then use a rounding algorithm for the generalized-assignment problem to "transfer" this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.
Cite as

Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, and Chaitanya Swamy. Approximation Algorithms for Minimum-Load k-Facility Location. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 17-33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{ahmadian_et_al:LIPIcs.APPROX-RANDOM.2014.17,
  author =	{Ahmadian, Sara and Behsaz, Babak and Friggstad, Zachary and Jorati, Amin and Salavatipour, Mohammad R. and Swamy, Chaitanya},
  title =	{{Approximation Algorithms for Minimum-Load k-Facility Location}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{17--33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.17},
  URN =		{urn:nbn:de:0030-drops-47154},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.17},
  annote =	{Keywords: approximation algorithms, min-max star cover, facility location, line metrics}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.34
The Cover Number of a Matrix and its Algorithmic Applications

Authors: Noga Alon, Troy Lee, and Adi Shraibman

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
Given a matrix A, we study how many epsilon-cubes are required to cover the convex hull of the columns of A. We show bounds on this cover number in terms of VC dimension and the gamma_2 norm and give algorithms for enumerating elements of a cover. This leads to algorithms for computing approximate Nash equilibria that unify and extend several previous results in the literature. Moreover, our approximation algorithms can be applied quite generally to a family of quadratic optimization problems that also includes finding the k-by-k combinatorial rectangle of a matrix. In particular, for this problem we give the first quasi-polynomial time additive approximation algorithm that works for any matrix A in [0,1]^{m x n}.
Cite as

Noga Alon, Troy Lee, and Adi Shraibman. The Cover Number of a Matrix and its Algorithmic Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 34-47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.APPROX-RANDOM.2014.34,
  author =	{Alon, Noga and Lee, Troy and Shraibman, Adi},
  title =	{{The Cover Number of a Matrix and its Algorithmic Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{34--47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.34},
  URN =		{urn:nbn:de:0030-drops-46865},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.34},
  annote =	{Keywords: Approximation algorithms, Approximate Nash equilibria, Cover number, VC dimension}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.48
Network Design with Coverage Costs

Authors: Siddharth Barman, Shuchi Chawla, and Seeun Umboh

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We study network design with a cost structure motivated by redundancy in data traffic. We are given a graph, g groups of terminals, and a universe of data packets. Each group of terminals desires a subset of the packets from its respective source. The cost of routing traffic on any edge in the network is proportional to the total size of the distinct packets that the edge carries. Our goal is to find a minimum cost routing. We focus on two settings. In the first, the collection of packet sets desired by source-sink pairs is laminar. For this setting, we present a primal-dual based 2-approximation, improving upon a logarithmic approximation due to Barman and Chawla (2012){BC12}. In the second setting, packet sets can have non-trivial intersection. We focus on the case where each packet is desired by either a single terminal group or by all of the groups. This setting does not admit an O(log^{{1}/{4} - gamma} g)-approximation for any constant gamma under a standard assumption; we present an O(log g)-approximation when the graph is unweighted. Our approximation for the second setting is based on a novel spanner-type construction in unweighted graphs that, given a collection of g vertex subsets, finds a subgraph of cost only a constant factor more than the minimum spanning tree of the graph, such that every subset in the collection has a Steiner tree in the subgraph of cost at most O(log g) that of its minimum Steiner tree in the original graph. We call such a subgraph a group spanner.
Cite as

Siddharth Barman, Shuchi Chawla, and Seeun Umboh. Network Design with Coverage Costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 48-63, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{barman_et_al:LIPIcs.APPROX-RANDOM.2014.48,
  author =	{Barman, Siddharth and Chawla, Shuchi and Umboh, Seeun},
  title =	{{Network Design with Coverage Costs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{48--63},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.48},
  URN =		{urn:nbn:de:0030-drops-46876},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.48},
  annote =	{Keywords: Network Design, Spanner, Primal Dual Method, Traffic Redundancy}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.64
Online Set Cover with Set Requests

Authors: Kshipra Bhawalkar, Sreenivas Gollapudi, and Debmalya Panigrahi

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We consider a generic online allocation problem that generalizes the classical online set cover framework by considering requests comprising a set of elements rather than a single element. This problem has multiple applications in cloud computing, crowd sourcing, facility planning, etc. Formally, it is an online covering problem where each online step comprises an offline covering problem. In addition, the covering sets are capacitated, leading to packing constraints. We give a randomized algorithm for this problem that has a nearly tight competitive ratio in both objectives: overall cost and maximum capacity violation. Our main technical tool is an online algorithm for packing/covering LPs with nested constraints, which may be of interest in other applications as well.
Cite as

Kshipra Bhawalkar, Sreenivas Gollapudi, and Debmalya Panigrahi. Online Set Cover with Set Requests. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 64-79, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{bhawalkar_et_al:LIPIcs.APPROX-RANDOM.2014.64,
  author =	{Bhawalkar, Kshipra and Gollapudi, Sreenivas and Panigrahi, Debmalya},
  title =	{{Online Set Cover with Set Requests}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{64--79},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.64},
  URN =		{urn:nbn:de:0030-drops-46883},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.64},
  annote =	{Keywords: Online Algorithms, Set Cover}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.80
Lowest Degree k-Spanner: Approximation and Hardness

Authors: Eden Chlamtác and Michael Dinitz

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
A k-spanner is a subgraph in which distances are approximately preserved, up to some given stretch factor k. We focus on the following problem: Given a graph and a value k, can we find a k-spanner that minimizes the maximum degree? While reasonably strong bounds are known for some spanner problems, they almost all involve minimizing the total number of edges. Switching the objective to the degree introduces significant new challenges, and currently the only known approximation bound is an O~(Delta^(3-2*sqrt(2)))-approximation for the special case when k = 2 [Chlamtac, Dinitz, Krauthgamer FOCS 2012] (where Delta is the maximum degree in the input graph). In this paper we give the first non-trivial algorithm and polynomial-factor hardness of approximation for the case of general k. Specifically, we give an LP-based O~(Delta^((1-1/k)^2) )-approximation and prove that it is hard to approximate the optimum to within Delta^Omega(1/k) when the graph is undirected, and to within Delta^Omega(1) when it is directed.
Cite as

Eden Chlamtác and Michael Dinitz. Lowest Degree k-Spanner: Approximation and Hardness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 80-95, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chlamtac_et_al:LIPIcs.APPROX-RANDOM.2014.80,
  author =	{Chlamt\'{a}c, Eden and Dinitz, Michael},
  title =	{{Lowest Degree k-Spanner: Approximation and Hardness}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{80--95},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.80},
  URN =		{urn:nbn:de:0030-drops-46894},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.80},
  annote =	{Keywords: Graph spanners, approximation algorithms, hardness of approximation}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.96
Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching

Authors: Michael Crouch and Daniel M. Stubbs

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We present a (4 + epsilon) approximation algorithm for weighted graph matching which applies in the semistreaming, sliding window, and MapReduce models; this single algorithm improves the previous best algorithm in each model. The algorithm operates by reducing the maximum-weight matching problem to a polylog number of copies of the maximum-cardinality matching problem. The algorithm also extends to provide approximation guarantees for the more general problem of finding weighted independent sets in p-systems (which include intersections of p matroids and p-bounded hypergraph matching).
Cite as

Michael Crouch and Daniel M. Stubbs. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 96-104, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{crouch_et_al:LIPIcs.APPROX-RANDOM.2014.96,
  author =	{Crouch, Michael and Stubbs, Daniel M.},
  title =	{{Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{96--104},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.96},
  URN =		{urn:nbn:de:0030-drops-46907},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.96},
  annote =	{Keywords: Streaming Algorithms, Graph Matching, Weighted Graph Matching, MapReduce, Independence Systems}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.105
Guruswami-Sinop Rounding without Higher Level Lasserre

Authors: Amit Deshpande and Rakesh Venkat

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
Guruswami and Sinop give a O(1/delta) approximation guarantee for the non-uniform Sparsest Cut problem by solving O(r)-level Lasserre semidefinite constraints, provided that the generalized eigenvalues of the Laplacians of the cost and demand graphs satisfy a certain spectral condition, namely, the (r+1)-th generalized eigenvalue is at least OPT/(1-delta). Their key idea is a rounding technique that first maps a vector-valued solution to [0,1] using appropriately scaled projections onto Lasserre vectors. In this paper, we show that similar projections and analysis can be obtained using only l_2^2 triangle inequality constraints. This results in a O(r/delta^2) approximation guarantee for the non-uniform Sparsest Cut problem by adding only l_2^2 triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, the (r+1)-th generalized eigenvalue is at least OPT/(1-delta), holds.
Cite as

Amit Deshpande and Rakesh Venkat. Guruswami-Sinop Rounding without Higher Level Lasserre. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 105-114, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{deshpande_et_al:LIPIcs.APPROX-RANDOM.2014.105,
  author =	{Deshpande, Amit and Venkat, Rakesh},
  title =	{{Guruswami-Sinop Rounding without Higher Level Lasserre}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{105--114},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.105},
  URN =		{urn:nbn:de:0030-drops-46911},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.105},
  annote =	{Keywords: Sparsest Cut, Lasserre Hierarchy, Metric embeddings}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.115
Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights

Authors: Michael Dinitz, Guy Kortsarz, and Zeev Nutov

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
In the Steiner k-Forest problem we are given an edge weighted graph, a collection D of node pairs, and an integer k \leq |D|. The goal is to find a minimum cost subgraph that connects at least k pairs. The best known ratio for this problem is min{O(sqrt{n}),O(sqrt{k})} [Gupta et al., 2008]. In [Gupta et al., 2008] it is also shown that ratio rho for Steiner k-Forest implies ratio O(rho log^2 n) for the Dial-a-Ride problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most k objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from [Gupta et al., 2008], has ratio O(sqrt{n}) [Charikar and Raghavachari, 1998]. We obtain ratio n^{0.448} for Steiner k-Forest and Dial-a-Ride with unit weights, breaking the O(sqrt{n}) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(n^{epsilon}), then one can achieve ratio O(n^{(1+epsilon) 0.448}), which is less than sqrt{n} if epsilon is small enough. To prove our main result we consider the following generalization of the Minimum k-Edge Subgraph (Mk-ES) problem, which we call Min-Cost l-Edge-Profit Subgraph (MCl-EPS): Given a graph G=(V,E) with edge-profits p={p_e: e in E} and node-costs c={c_v: v in V}, and a lower profit bound l, find a minimum node-cost subgraph of G of edge profit at least l. The Mk-ES problem is a special case of MCl-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is n^{3-2*sqrt{2} + epsilon} (note that 3-2*sqrt{2} < 0.1716). We extend this ratio to MCl-EPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest.
Cite as

Michael Dinitz, Guy Kortsarz, and Zeev Nutov. Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 115-127, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.APPROX-RANDOM.2014.115,
  author =	{Dinitz, Michael and Kortsarz, Guy and Nutov, Zeev},
  title =	{{Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{115--127},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.115},
  URN =		{urn:nbn:de:0030-drops-46925},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.115},
  annote =	{Keywords: k-Steiner Forest; Uniform weights; Densest k-Subgraph; Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.128
Computing Opaque Interior Barriers à la Shermer

Authors: Adrian Dumitrescu, Minghui Jiang, and Csaba D. Tóth

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given polygon was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the polygon. In 1991 Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex n-gon. He conjectured that the barrier found by his algorithm is optimal, however this was refuted recently by Provan et al. Here we give a Shermer like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in O(n) time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm.
Cite as

Adrian Dumitrescu, Minghui Jiang, and Csaba D. Tóth. Computing Opaque Interior Barriers à la Shermer. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 128-143, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.APPROX-RANDOM.2014.128,
  author =	{Dumitrescu, Adrian and Jiang, Minghui and T\'{o}th, Csaba D.},
  title =	{{Computing Opaque Interior Barriers \`{a} la Shermer}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{128--143},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.128},
  URN =		{urn:nbn:de:0030-drops-46938},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.128},
  annote =	{Keywords: Opaque barrier, approximation algorithm, isoperimetric inequality}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.144
Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture

Authors: Alina Ene and Jan Vondrák

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We consider the Minimum Submodular Cost Allocation (MSCA) problem. In this problem, we are given k submodular cost functions f_1, ... , f_k: 2^V -> R_+ and the goal is to partition V into k sets A_1, ..., A_k so as to minimize the total cost sum_{i = 1}^k f_i(A_i). We show that MSCA is inapproximable within any multiplicative factor even in very restricted settings; prior to our work, only Set Cover hardness was known. In light of this negative result, we turn our attention to special cases of the problem. We consider the setting in which each function f_i satisfies f_i = g_i + h, where each g_i is monotone submodular and h is (possibly non-monotone) submodular. We give an O(k log |V|) approximation for this problem. We provide some evidence that a factor of k may be necessary, even in the special case of HyperLabel. In particular, we formulate a simplex-coloring conjecture that implies a Unique-Games-hardness of (k - 1 - epsilon) for k-uniform HyperLabel and label set [k]. We provide a proof of the simplex-coloring conjecture for k=3.
Cite as

Alina Ene and Jan Vondrák. Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 144-159, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.APPROX-RANDOM.2014.144,
  author =	{Ene, Alina and Vondr\'{a}k, Jan},
  title =	{{Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{144--159},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.144},
  URN =		{urn:nbn:de:0030-drops-46943},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.144},
  annote =	{Keywords: Minimum Cost Submodular Allocation, Submodular Optimization, Hypergraph Labeling}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.160
Constrained Monotone Function Maximization and the Supermodular Degree

Authors: Moran Feldman and Rani Izsak

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
The problem of maximizing a constrained monotone set function has many practical applications and generalizes many combinatorial problems such as k-Coverage, Max-SAT, Set Packing, Maximum Independent Set and Welfare Maximization. Unfortunately, it is generally not possible to maximize a monotone set function up to an acceptable approximation ratio, even subject to simple constraints. One highly studied approach to cope with this hardness is to restrict the set function, for example, by requiring it to be submodular. An outstanding disadvantage of imposing such a restriction on the set function is that no result is implied for set functions deviating from the restriction, even slightly. A more flexible approach, studied by Feige and Izsak [ITCS 2013], is to design an approximation algorithm whose approximation ratio depends on the complexity of the instance, as measured by some complexity measure. Specifically, they introduced a complexity measure called supermodular degree, measuring deviation from submodularity, and designed an algorithm for the welfare maximization problem with an approximation ratio that depends on this measure. In this work, we give the first (to the best of our knowledge) algorithm for maximizing an arbitrary monotone set function, subject to a k-extendible system. This class of constraints captures, for example, the intersection of k-matroids (note that a single matroid constraint is sufficient to capture the welfare maximization problem). Our approximation ratio deteriorates gracefully with the complexity of the set function and k. Our work can be seen as generalizing both the classic result of Fisher, Nemhauser and Wolsey [Mathematical Programming Study 1978], for maximizing a submodular set function subject to a k-extendible system, and the result of Feige and Izsak for the welfare maximization problem. Moreover, when our algorithm is applied to each one of these simpler cases, it obtains the same approximation ratio as of the respective original work. That is, the generalization does not incur any penalty. Finally, we also consider the less general problem of maximizing a monotone set function subject to a uniform matroid constraint, and give a somewhat better approximation ratio for it.
Cite as

Moran Feldman and Rani Izsak. Constrained Monotone Function Maximization and the Supermodular Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 160-175, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.APPROX-RANDOM.2014.160,
  author =	{Feldman, Moran and Izsak, Rani},
  title =	{{Constrained Monotone Function Maximization and the Supermodular Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{160--175},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.160},
  URN =		{urn:nbn:de:0030-drops-46950},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.160},
  annote =	{Keywords: supermodular degree, set function, submodular, matroid, extendible system}
}
  • Refine by Author
  • 2 Brody, Joshua
  • 2 Devanur, Nikhil R.
  • 2 Dinitz, Michael
  • 2 Galanis, Andreas
  • 2 Ganor, Anat
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 Approximation Algorithms
  • 3 Approximation algorithms
  • 3 Streaming Algorithms
  • 3 approximation algorithms
  • 2 Communication complexity
  • Show More...

  • Refine by Type
  • 63 document
  • 1 volume

  • Refine by Publication Year
  • 64 2014

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact