Search Results

Documents authored by Kortsarz, Guy

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.3
Degrees and Network Design: New Problems and Approximations

Authors: Michael Dinitz, Guy Kortsarz, and Shi Li

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

Abstract
While much of network design focuses mostly on cost (number or weight of edges), node degrees have also played an important role. They have traditionally either appeared as an objective, to minimize the maximum degree (e.g., the Minimum Degree Spanning Tree problem), or as constraints that might be violated to give bicriteria approximations (e.g., the Minimum Cost Degree Bounded Spanning Tree problem). We extend the study of degrees in network design in two ways. First, we introduce and study a new variant of the Survivable Network Design Problem where in addition to the traditional objective of minimizing the cost of the chosen edges, we add a constraint that the 𝓁_p-norm of the node degree vector is bounded by an input parameter. This interpolates between the classical settings of maximum degree (the 𝓁_∞-norm) and the number of edges (the 𝓁₁-degree), and has natural applications in distributed systems and VLSI design. We give a constant bicriteria approximation in both measures using convex programming. Second, we provide a polylogarithmic bicriteria approximation for the Degree Bounded Group Steiner problem on bounded treewidth graphs, solving an open problem from [Guy Kortsarz and Zeev Nutov, 2022] and [X. Guo et al., 2022].
Cite as

Michael Dinitz, Guy Kortsarz, and Shi Li. Degrees and Network Design: New Problems and Approximations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.APPROX/RANDOM.2024.3,
  author =	{Dinitz, Michael and Kortsarz, Guy and Li, Shi},
  title =	{{Degrees and Network Design: New Problems and Approximations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.3},
  URN =		{urn:nbn:de:0030-drops-209969},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.3},
  annote =	{Keywords: Network Design, Degrees}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.21
The Telephone k-Multicast Problem

Authors: Daniel Hathcock, Guy Kortsarz, and R. Ravi

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

Abstract
We consider minimum time multicasting problems in directed and undirected graphs: given a root node and a subset of t terminal nodes, multicasting seeks to find the minimum number of rounds within which all terminals can be informed with a message originating at the root. In each round, the telephone model we study allows the information to move via a matching from the informed nodes to the uninformed nodes. Since minimum time multicasting in digraphs is poorly understood compared to the undirected variant, we study an intermediate problem in undirected graphs that specifies a target k < t, and requires the only k of the terminals be informed in the minimum number of rounds. For this problem, we improve implications of prior results and obtain an Õ(t^{1/3}) multiplicative approximation. For the directed version, we obtain an additive Õ(k^{1/2}) approximation algorithm (with a poly-logarithmic multiplicative factor). Our algorithms are based on reductions to the related problems of finding k-trees of minimum poise (sum of maximum degree and diameter) and applying a combination of greedy network decomposition techniques and set covering under partition matroid constraints.
Cite as

Daniel Hathcock, Guy Kortsarz, and R. Ravi. The Telephone k-Multicast Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hathcock_et_al:LIPIcs.APPROX/RANDOM.2024.21,
  author =	{Hathcock, Daniel and Kortsarz, Guy and Ravi, R.},
  title =	{{The Telephone k-Multicast Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.21},
  URN =		{urn:nbn:de:0030-drops-210148},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.21},
  annote =	{Keywords: Network Design, Multicast, Steiner Poise}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.41
Relative Survivable Network Design

Authors: Michael Dinitz, Ama Koranteng, and Guy Kortsarz

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

Abstract
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum k-Edge-Connected Spanning Subgraph problem (k-ECSS), as well as nonuniform demands such as the Survivable Network Design problem. A weakness of these formulations, though, is that we are not able to ask for fault-tolerance larger than the connectivity. Taking inspiration from recent definitions and progress in graph spanners, we introduce and study new variants of these problems under a notion of relative fault-tolerance. Informally, we require not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that two nodes are connected if there are a bounded number of faults and the two nodes are connected in the underlying graph post-faults. That is, the subgraph we build must "behave" identically to the underlying graph with respect to connectivity after bounded faults. We define and introduce these problems, and provide the first approximation algorithms: a (1+4/k)-approximation for the unweighted relative version of k-ECSS, a 2-approximation for the weighted relative version of k-ECSS, and a 27/4-approximation for the special case of Relative Survivable Network Design with only a single demand with a connectivity requirement of 3. To obtain these results, we introduce a number of technical ideas that may of independent interest. First, we give a generalization of Jain’s iterative rounding analysis that works even when the cut-requirement function is not weakly supermodular, but instead satisfies a weaker definition we introduce and term local weak supermodularity. Second, we prove a structure theorem and design an approximation algorithm utilizing a new decomposition based on important separators, which are structures commonly used in fixed-parameter algorithms that have not commonly been used in approximation algorithms.
Cite as

Michael Dinitz, Ama Koranteng, and Guy Kortsarz. Relative Survivable Network Design. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.APPROX/RANDOM.2022.41,
  author =	{Dinitz, Michael and Koranteng, Ama and Kortsarz, Guy},
  title =	{{Relative Survivable Network Design}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{41:1--41:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.41},
  URN =		{urn:nbn:de:0030-drops-171632},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.41},
  annote =	{Keywords: Fault Tolerance, Network Design}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.39
On Approximating Degree-Bounded Network Design Problems

Authors: Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, and Jiayi Xian

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

Abstract
Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph G = (V, E) with edge costs c ∈ ℝ_{≥ 0}^E, a root r ∈ V and k terminals K ⊆ V, we need to output a minimum-cost arborescence in G that contains an rrightarrow t path for every t ∈ K. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time O(log²k/log log k)-approximation algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound d_v on each vertex v ∈ V, and we require that every vertex v in the output tree has at most d_v children. We give a quasi-polynomial time (O(log n log k), O(log² n))-bicriteria approximation: The algorithm produces a solution with cost at most O(log nlog k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O(log²n). This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O(log²n) is an O(log n)-factor away from the approximation lower bound of Ω(log n) from the Set Cover hardness. The hardness result holds even on the special case of the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an (O(log nlog k), O(log n))-bicriteria approximation algorithm for DB-GST-T.
Cite as

Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, and Jiayi Xian. On Approximating Degree-Bounded Network Design Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 39:1-39:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.APPROX/RANDOM.2020.39,
  author =	{Guo, Xiangyu and Kortsarz, Guy and Laekhanukit, Bundit and Li, Shi and Vaz, Daniel and Xian, Jiayi},
  title =	{{On Approximating Degree-Bounded Network Design Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{39:1--39:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.39},
  URN =		{urn:nbn:de:0030-drops-126420},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.39},
  annote =	{Keywords: Directed Steiner Tree, Group Steiner Tree, degree-bounded}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.20
Approximating Activation Edge-Cover and Facility Location Problems

Authors: Zeev Nutov, Guy Kortsarz, and Eli Shalom

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v, the opening cost of v is at most theta times the service cost of u? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G=(V,E), a set R subseteq V of terminals, and thresholds {t^e_u,t^e_v} for each uv-edge e in E. The goal is to find an assignment a={a_v:v in V} to the nodes minimizing sum_{v in V} a_v, such that the edge set E_a={e=uv: a_u >= t^e_u, a_v >= t^e_v} activated by a covers R. We obtain ratio 1+max_{x>=1}(ln x)/(1+x/theta)~= ln theta - ln ln theta for the problem, where theta is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of {Facility Location}. If for each facility all service costs are identical then we show a better ratio 1+max_{k in N}(H_k-1)/(1+k/theta), where H_k=sum_{i=1}^k 1/i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of [Calinescu et al, 2019] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73/60~=1.217 of [Calinescu et al, 2019] to 1555/1347~=1.155.
Cite as

Zeev Nutov, Guy Kortsarz, and Eli Shalom. Approximating Activation Edge-Cover and Facility Location Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nutov_et_al:LIPIcs.MFCS.2019.20,
  author =	{Nutov, Zeev and Kortsarz, Guy and Shalom, Eli},
  title =	{{Approximating Activation Edge-Cover and Facility Location Problems}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.20},
  URN =		{urn:nbn:de:0030-drops-109642},
  doi =		{10.4230/LIPIcs.MFCS.2019.20},
  annote =	{Keywords: generalized min-covering problem, activation edge-cover, facility location, minimum power, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.158
Spanning Trees With Edge Conflicts and Wireless Connectivity

Authors: Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, and Tigran Tonoyan

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close - thus, the available pairs are specified with a link graph {L}=(V,E). Also, signal attenuation need not follow a nice geometric formula - hence, interference is modeled by a conflict (hyper)graph {C}=(E,F) on the links. The objective is to maximize the efficiency of the communication, or equivalently, to minimize the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the interference graph. Specifically, we give a simple algorithm that attains a O(rho log n)-approximation, where n is the number of nodes and rho is the inductive independence, and show that near-linear dependence on rho is also necessary. We also treat an extension to Steiner trees, modeling multicasting, and obtain a comparable result. Our results suggest that several canonical assumptions of geometry, regularity and "niceness" in wireless settings can sometimes be relaxed without a significant hit in algorithm performance.
Cite as

Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, and Tigran Tonoyan. Spanning Trees With Edge Conflicts and Wireless Connectivity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 158:1-158:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.ICALP.2018.158,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Kortsarz, Guy and Mitra, Pradipta and Tonoyan, Tigran},
  title =	{{Spanning Trees With Edge Conflicts and Wireless Connectivity}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{158:1--158:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.158},
  URN =		{urn:nbn:de:0030-drops-91627},
  doi =		{10.4230/LIPIcs.ICALP.2018.158},
  annote =	{Keywords: spanning trees, wireless capacity, aggregation, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.6
The Densest k-Subhypergraph Problem

Authors: Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca

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

Abstract
The Densest k-Subgraph (DkS) problem, and its corresponding minimization problem Smallest p-Edge Subgraph (SpES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out). In this paper we generalize both DkS and SpES from graphs to hypergraphs. We consider the Densest k-Subhypergraph problem (given a hypergraph (V, E), find a subset W subseteq V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union problem (given a hypergraph, choose p of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest non-graph setting. For this case we provide an O(n^{4(4-sqrt{3})/13 + epsilon}) <= O(n^{0.697831+epsilon})-approximation (for arbitrary constant epsilon > 0) for Densest k-Subhypergraph and an ~O(n^{2/5})-approximation for Minimum p-Union. We also give an O(sqrt{m})-approximation for Minimum p-Union in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances.
Cite as

Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca. The Densest k-Subhypergraph Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chlamtac_et_al:LIPIcs.APPROX-RANDOM.2016.6,
  author =	{Chlamtac, Eden and Dinitz, Michael and Konrad, Christian and Kortsarz, Guy and Rabanca, George},
  title =	{{The Densest k-Subhypergraph Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.6},
  URN =		{urn:nbn:de:0030-drops-66298},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.6},
  annote =	{Keywords: Hypergraphs, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.13
LP-Relaxations for Tree Augmentation

Authors: Guy Kortsarz and Zeev Nutov

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

Abstract
In the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T+F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for TAP. In this paper we introduce two different LP-relaxations, and for each of them give a simple algorithm that computes a feasible solution for TAP of size at most 7/4 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case.
Cite as

Guy Kortsarz and Zeev Nutov. LP-Relaxations for Tree Augmentation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kortsarz_et_al:LIPIcs.APPROX-RANDOM.2016.13,
  author =	{Kortsarz, Guy and Nutov, Zeev},
  title =	{{LP-Relaxations for Tree Augmentation}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.13},
  URN =		{urn:nbn:de:0030-drops-66366},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.13},
  annote =	{Keywords: Tree Augmentation; LP-relaxation; Laminar family; Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.6
Bicovering: Covering Edges With Two Small Subsets of Vertices

Authors: Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We study the following basic problem called Bi-Covering. Given a graph G(V, E), find two (not necessarily disjoint) sets A subseteq V and B subseteq V such that A union B = V and that every edge e belongs to either the graph induced by A or to the graph induced by B. The goal is to minimize max{|A|, |B|}. This is the most simple case of the Channel Allocation problem [Gandhi et al., Networks, 2006]. A solution that outputs V,emptyset gives ratio at most 2. We show that under the similar Strong Unique Game Conjecture by [Bansal-Khot, FOCS, 2009] there is no 2 - epsilon ratio algorithm for the problem, for any constant epsilon > 0. Given a bipartite graph, Max-bi-clique is a problem of finding largest k*k complete bipartite sub graph. For Max-bi-clique problem, a constant factor hardness was known under random 3-SAT hypothesis of Feige [Feige, STOC, 2002] and also under the assumption that NP !subseteq intersection_{epsilon > 0} BPTIME(2^{n^{epsilon}}) [Khot, SIAM J. on Comp., 2011]. It was an open problem in [Ambühl et. al., SIAM J. on Comp., 2011] to prove inapproximability of Max-bi-clique assuming weaker conjecture. Our result implies similar hardness result assuming the Strong Unique Games Conjecture. On the algorithmic side, we also give better than 2 approximation for Bi-Covering on numerous special graph classes. In particular, we get 1.876 approximation for Chordal graphs, exact algorithm for Interval Graphs, 1 + o(1) for Minor Free Graph, 2 - 4*delta/3 for graphs with minimum degree delta*n, 2/(1+delta^2/8) for delta-vertex expander, 8/5 for Split Graphs, 2 - (6/5)*1/d for graphs with minimum constant degree d etc. Our algorithmic results are quite non-trivial. In achieving these results, we use various known structural results about the graphs, combined with the techniques that we develop tailored to getting better than 2 approximation.
Cite as

Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz. Bicovering: Covering Edges With Two Small Subsets of Vertices. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ICALP.2016.6,
  author =	{Bhangale, Amey and Gandhi, Rajiv and Hajiaghayi, Mohammad Taghi and Khandekar, Rohit and Kortsarz, Guy},
  title =	{{Bicovering: Covering Edges With Two Small Subsets of Vertices}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.6},
  URN =		{urn:nbn:de:0030-drops-62728},
  doi =		{10.4230/LIPIcs.ICALP.2016.6},
  annote =	{Keywords: Bi-covering, Unique Games, Max Bi-clique}
}
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/DagSemProc.09511.4
Approximating minimum cost connectivity problems

Authors: Guy Kortsarz and Zeev Nutov

Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)

Abstract
We survey approximation algorithms of connectivity problems. The survey presented describing various techniques. In the talk the following techniques and results are presented. 1)Outconnectivity: Its well known that there exists a polynomial time algorithm to solve the problems of finding an edge k-outconnected from r subgraph [EDMONDS] and a vertex k-outconnectivity subgraph from r [Frank-Tardos] . We show how to use this to obtain a ratio 2 approximation for the min cost edge k-connectivity problem. 2)The critical cycle theorem of Mader: We state a fundamental theorem of Mader and use it to provide a 1+(k-1)/n ratio approximation for the min cost vertex k-connected subgraph, in the metric case. We also show results for the min power vertex k-connected problem using this lemma. We show that the min power is equivalent to the min-cost case with respect to approximation. 3)Laminarity and uncrossing: We use the well known laminarity of a BFS solution and show a simple new proof due to Ravi et al for Jain's 2 approximation for Steiner network.
Cite as

Guy Kortsarz and Zeev Nutov. Approximating minimum cost connectivity problems. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{kortsarz_et_al:DagSemProc.09511.4,
  author =	{Kortsarz, Guy and Nutov, Zeev},
  title =	{{Approximating minimum cost connectivity problems}},
  booktitle =	{Parameterized complexity and approximation algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9511},
  editor =	{Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.4},
  URN =		{urn:nbn:de:0030-drops-24975},
  doi =		{10.4230/DagSemProc.09511.4},
  annote =	{Keywords: Connectivity, laminar, uncrossing, Mader's Theorem, power problems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2324
Approximating Fault-Tolerant Group-Steiner Problems

Authors: Rohit Khandekar, Guy Kortsarz, and Zeev Nutov

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
In this paper, we initiate the study of designing approximation algorithms for {\sf Fault-Tolerant Group-Steiner} ({\sf FTGS}) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In {\sf Fault-Tolerant Group-Steiner} problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths from each group to the root. We present approximation algorithms and hardness results for several variants of this basic problem, e.g., edge-costs vs. vertex-costs, edge-connectivity vs. vertex-connectivity, and $2$-connecting from each group a single vertex vs. many vertices. Main contributions of our paper include the introduction of very general structural lemmas on connectivity and a charging scheme that may find more applications in the future. Our algorithmic results are supplemented by inapproximability results, which are tight in some cases. Our algorithms employ a variety of techniques. For the edge-connectivity variant, we use a primal-dual based algorithm for covering an {\em uncros\-sable} set-family, while for the vertex-connectivity version, we prove a new graph-theoretic lemma that shows equivalence between obtaining two vertex-disjoint paths from two vertices and $2$-connecting a carefully chosen single vertex. To handle large group-sizes, we use a $p$-Steiner tree algorithm to identify the ``correct'' pair of terminals from each group to be connected to the root. We also use a non-trivial charging scheme to improve the approximation ratio for the most general problem we consider.
Cite as

Rohit Khandekar, Guy Kortsarz, and Zeev Nutov. Approximating Fault-Tolerant Group-Steiner Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 263-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{khandekar_et_al:LIPIcs.FSTTCS.2009.2324,
  author =	{Khandekar, Rohit and Kortsarz, Guy and Nutov, Zeev},
  title =	{{Approximating Fault-Tolerant Group-Steiner Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{263--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2324},
  URN =		{urn:nbn:de:0030-drops-23243},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2324},
  annote =	{Keywords: Fault-tolerance, group Steiner problem, edge-disjointness, vertex-disjointness, approximation, connectivity}
}
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact