Search Results

Documents authored by Friggstad, Zachary

Document
DOI: 10.4230/LIPIcs.SWAT.2024.21
Approximating Minimum Sum Coloring with Bundles

Authors: Seyed Parsa Darbouy and Zachary Friggstad

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
In the Minimum Sum Coloring with Bundles problem, we are given an undirected graph G = (V,E) and (not necessarily disjoint) bundles V_1, V_2, …, V_p ⊆ V with associated weights w_1, …, w_p ≥ 0. The goal is to give a proper coloring of G using positive integers to minimize the weighted average/total completion time of all bundles, where the completion time of a bundle is the maximum integer assigned to one of its nodes. This is a common generalization of the classic Minimum Sum Coloring problem, i.e. when all bundles are singleton nodes, and the classic Chromatic Number problem, i.e. the only bundle is all of V. Despite its generality as an extension of Minimum Sum Coloring, only very special cases have been studied with the most common being the line graph L(H) of a graph H (also known as Coflow Scheduling). We provide the first constant-factor approximation in perfect graphs and, more generally, graphs whose chromatic number is within a constant factor of the maximum clique size in any induced subgraph. For example, we obtain constant-factor approximations for graphs that are well-studied in minimum sum coloring such as interval graphs and unit disk graphs. Next, we extend our results to get constant-factor approximations for a general model where the bundles are disjoint (i.e. can be thought of as jobs brought by the corresponding client) and we are only permitted to color/schedule a bounded number of jobs from each bundle at any given time. Specifically, we get constant-factor approximations for this model if the nodes of graph G have an ordering v_1, v_2, …, v_n such that the left-neighborhood N_𝓁(v_i) : = {v_j : j < i, v_iv_j ∈ E} can be covered by O(1) cliques. For example, this applies to chordal graphs, unit disc graphs, and circular arc graphs.
Cite as

Seyed Parsa Darbouy and Zachary Friggstad. Approximating Minimum Sum Coloring with Bundles. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{darbouy_et_al:LIPIcs.SWAT.2024.21,
  author =	{Darbouy, Seyed Parsa and Friggstad, Zachary},
  title =	{{Approximating Minimum Sum Coloring with Bundles}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.21},
  URN =		{urn:nbn:de:0030-drops-200611},
  doi =		{10.4230/LIPIcs.SWAT.2024.21},
  annote =	{Keywords: Approximation Algorithms, Scheduling, Coloring}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.23
A Logarithmic Integrality Gap for Generalizations of Quasi-Bipartite Instances of Directed Steiner Tree

Authors: Zachary Friggstad and Hao Sun

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
In the classic Directed Steiner Tree problem (DST), we are given an edge-weighted directed graph G = (V,E) with n nodes, a specified root node r ∈ V, and k terminals X ⊆ V-{r}. The goal is to find the cheapest F ⊆ E such that r can reach any terminal using only edges in F. Designing approximation algorithms for DST is quite challenging, to date the best approximation guarantee of a polynomial-time algorithm for DST is O(k^ε) for any constant ε > 0 [Charikar et al., 1999]. For network design problems like DST, one often relies on natural cut-based linear programming (LP) relaxations to design approximation algorithms. In general, the integrality gap of such an LP for DST is known to have a polynomial integrality gap lower bound [Zosin and Khuller, 2002; Li and Laekhanukit, 2021]. So particular interest has been invested in special cases or in strengthenings of this LP. In this work, we show the integrality gap is only O(log k) for instances of DST where no Steiner node has both an edge from another Steiner node and an edge to another Steiner node, i.e. the longest path using only Steiner nodes has length at most 1. This generalizes the well-studied case of quasi-bipartite DST where no edge has both endpoints being Steiner nodes. Our result is also optimal in the sense that the integrality gap can be as bad as poly(n) even if the longest path with only Steiner nodes has length 2.
Cite as

Zachary Friggstad and Hao Sun. A Logarithmic Integrality Gap for Generalizations of Quasi-Bipartite Instances of Directed Steiner Tree. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.SWAT.2024.23,
  author =	{Friggstad, Zachary and Sun, Hao},
  title =	{{A Logarithmic Integrality Gap for Generalizations of Quasi-Bipartite Instances of Directed Steiner Tree}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.23},
  URN =		{urn:nbn:de:0030-drops-200638},
  doi =		{10.4230/LIPIcs.SWAT.2024.23},
  annote =	{Keywords: Steiner Tree, Approximation Algorithms, Linear Programming}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.13
A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs

Authors: Zachary Friggstad and Ramin Mousavi

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

Abstract
We give the first constant-factor approximation algorithm for quasi-bipartite instances of Directed Steiner Tree on graphs that exclude fixed minors. In particular, for K_r-minor-free graphs our approximation guarantee is O(r⋅√(log r)) and, further, for planar graphs our approximation guarantee is 20. Our algorithm uses the primal-dual scheme. We employ a more involved method of determining when to buy an edge while raising dual variables since, as we show, the natural primal-dual scheme fails to raise enough dual value to pay for the purchased solution. As a consequence, we also demonstrate integrality gap upper bounds on the standard cut-based linear programming relaxation for the Directed Steiner Tree instances we consider.
Cite as

Zachary Friggstad and Ramin Mousavi. A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.APPROX/RANDOM.2023.13,
  author =	{Friggstad, Zachary and Mousavi, Ramin},
  title =	{{A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.13},
  URN =		{urn:nbn:de:0030-drops-188389},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.13},
  annote =	{Keywords: Directed Steiner tree, Combinatorial optimization, approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.63
An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs

Authors: Zachary Friggstad and Ramin Mousavi

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We present an O(log k)-approximation for both the edge-weighted and node-weighted versions of Directed Steiner Tree in planar graphs where k is the number of terminals. We extend our approach to Multi-Rooted Directed Steiner Tree, in which we get a O(R+log k)-approximation for planar graphs for where R is the number of roots.
Cite as

Zachary Friggstad and Ramin Mousavi. An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ICALP.2023.63,
  author =	{Friggstad, Zachary and Mousavi, Ramin},
  title =	{{An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{63:1--63:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.63},
  URN =		{urn:nbn:de:0030-drops-181156},
  doi =		{10.4230/LIPIcs.ICALP.2023.63},
  annote =	{Keywords: Directed Steiner tree, Combinatorial optimization, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.8
Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP

Authors: Zachary Friggstad and Ramin Mousavi

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We initiate the study of the Bounded-Degree Subset Traveling Salesman problem (BDSTSP) in which we are given a graph G = (V,E) with edge cost c_e ≥ 0 on each edge e, degree bounds b_v ≥ 0 on each vertex v ∈ V and a subset of terminals X ⊆ V. The goal is to find a minimum-cost closed walk that spans all terminals and visits each vertex v ∈ V at most b_v/2 times. In this paper, we study bi-criteria approximations that find tours whose cost is within a constant-factor of the optimum tour length while violating the bounds b_v at each vertex by additive quantities. If X = V, an adaptation of the Christofides-Serdyukov algorithm yields a (3/2, +4)-approximation, that is the tour passes through each vertex at most b_v/2+2 times (the degree of v in the multiset of edges on the tour being at most b_v + 4). This is enabled through known results in bounded-degree Steiner trees and integrality of the bounded-degree Y-join polytope. The general case X ≠ V is more challenging since we cannot pass to the metric completion on X. However, it is at least simple to get a (5/3, +4)-bicriteria approximation by using ideas similar to Hoogeveen’s TSP-Path algorithm. Our main result is an improved approximation with marginally worse violations of the vertex bounds: a (13/8, +6)-approximation. We obtain this primarily through adapting the bounded-degree Steiner tree approximation to ensure certain "dangerous" nodes always have even degree in the resulting tree which allows us to bound the cost of the resulting degree-bounded Y-join. We also recover a (3/2, +8)-approximation for this general case.
Cite as

Zachary Friggstad and Ramin Mousavi. Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ISAAC.2022.8,
  author =	{Friggstad, Zachary and Mousavi, Ramin},
  title =	{{Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.8},
  URN =		{urn:nbn:de:0030-drops-172932},
  doi =		{10.4230/LIPIcs.ISAAC.2022.8},
  annote =	{Keywords: Linear programming, approximation algorithms, combinatorial optimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.56
Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters

Authors: Zachary Friggstad and Mahya Jamshidian

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We give an improved approximation algorithm for two related clustering problems. In the Minimum Sum of Radii clustering problem (MSR), we are to select k balls in a metric space to cover all points while minimizing the sum of the radii of these balls. In the Minimum Sum of Diameters clustering problem (MSD), we are to simply partition the points of a metric space into k parts while minimizing the sum of the diameters of these parts. We present a 3.389-approximation for MSR and a 6.546-approximation for MSD, improving over their respective 3.504 and 7.008 approximations developed by Charikar and Panigrahy (2001). In particular, our guarantee for MSD is better than twice our guarantee for MSR. Our approach refines a so-called bipoint rounding procedure of Charikar and Panigrahy’s algorithm by considering centering balls at some points that were not necessarily centers in the bipoint solution. This added versatility enables the analysis of our improved approximation guarantees. We also provide an alternative approach to finding the bipoint solution using a straightforward LP rounding procedure rather than a primal-dual algorithm.
Cite as

Zachary Friggstad and Mahya Jamshidian. Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ESA.2022.56,
  author =	{Friggstad, Zachary and Jamshidian, Mahya},
  title =	{{Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.56},
  URN =		{urn:nbn:de:0030-drops-169946},
  doi =		{10.4230/LIPIcs.ESA.2022.56},
  annote =	{Keywords: Approximation Algorithms, Clustering, Linear Programming}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.67
Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime

Authors: Zachary Friggstad and Chaitanya Swamy

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We investigate a genre of vehicle-routing problems (VRPs), that we call max-reward VRPs, wherein nodes located in a metric space have associated rewards that depend on their visiting times, and we seek a path that earns maximum reward. A prominent problem in this genre is deadline TSP, where nodes have deadlines and we seek a path that visits all nodes by their deadlines and earns maximum reward. Our main result is a constant-factor approximation for deadline TSP running in time O(n^O(log(nΔ))) in metric spaces with integer distances at most Δ. This is the first improvement over the approximation factor of O(log n) due to Bansal et al. [N. Bansal et al., 2004] in over 15 years (but is achieved in super-polynomial time). Our result provides the first concrete indication that log n is unlikely to be a real inapproximability barrier for deadline TSP, and raises the exciting possibility that deadline TSP might admit a polytime constant-factor approximation. At a high level, we obtain our result by carefully guessing an appropriate sequence of O(log (nΔ)) nodes appearing on the optimal path, and finding suitable paths between any two consecutive guessed nodes. We argue that the problem of finding a path between two consecutive guessed nodes can be relaxed to an instance of a special case of deadline TSP called point-to-point (P2P) orienteering. Any approximation algorithm for P2P orienteering can then be utilized in conjunction with either a greedy approach, or an LP-rounding approach, to find a good set of paths overall between every pair of guessed nodes. While concatenating these paths does not immediately yield a feasible solution, we argue that it can be covered by a constant number of feasible solutions. Overall our result therefore provides a novel reduction showing that any α-approximation for P2P orienteering can be leveraged to obtain an O(α)-approximation for deadline TSP in O(n^O(log nΔ)) time. Our results extend to yield the same guarantees (in approximation ratio and running time) for a substantial generalization of deadline TSP, where the reward obtained by a client is given by an arbitrary non-increasing function (specified by a value oracle) of its visiting time. Finally, we discuss applications of our results to variants of deadline TSP, including settings where both end-nodes are specified, nodes have release dates, and orienteering with time windows.
Cite as

Zachary Friggstad and Chaitanya Swamy. Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 67:1-67:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ICALP.2021.67,
  author =	{Friggstad, Zachary and Swamy, Chaitanya},
  title =	{{Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{67:1--67:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.67},
  URN =		{urn:nbn:de:0030-drops-141369},
  doi =		{10.4230/LIPIcs.ICALP.2021.67},
  annote =	{Keywords: Approximation algorithms, Vehicle routing problems, Deadline TSP, Orienteering}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.52
A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time

Authors: Zachary Friggstad and Chaitanya Swamy

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We consider the directed minimum latency problem (DirLat), wherein we seek a path P visiting all points (or clients) in a given asymmetric metric starting at a given root node r, so as to minimize the sum of the client waiting times, where the waiting time of a client v is the length of the r-v portion of P. We give the first constant-factor approximation guarantee for DirLat, but in quasi-polynomial time. Previously, a polynomial-time O(log n)-approximation was known [Z. Friggstad et al., 2013], and no better approximation guarantees were known even in quasi-polynomial time. A key ingredient of our result, and our chief technical contribution, is an extension of a recent result of [A. Köhne et al., 2019] showing that the integrality gap of the natural Held-Karp relaxation for asymmetric TSP-Path (ATSPP) is at most a constant, which itself builds on the breakthrough similar result established for asymmetric TSP (ATSP) by Svensson et al. [O. Svensson et al., 2018]. We show that the integrality gap of the Held-Karp relaxation for ATSPP is bounded by a constant even if the cut requirements of the LP relaxation are relaxed from x(δ^{in}(S)) ≥ 1 to x(δ^{in}(S)) ≥ ρ for some constant 1/2 < ρ ≤ 1. We also give a better approximation guarantee for the minimum total-regret problem, where the goal is to find a path P that minimizes the total time that nodes spend in excess of their shortest-path distances from r, which can be cast as a special case of DirLat involving so-called regret metrics.
Cite as

Zachary Friggstad and Chaitanya Swamy. A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ESA.2020.52,
  author =	{Friggstad, Zachary and Swamy, Chaitanya},
  title =	{{A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{52:1--52:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.52},
  URN =		{urn:nbn:de:0030-drops-129183},
  doi =		{10.4230/LIPIcs.ESA.2020.52},
  annote =	{Keywords: Approximation Algorithms, Directed Latency, TSP}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.5
Scheduling Problems over Network of Machines

Authors: Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, and Yifeng Zhang

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

Abstract
We consider scheduling problems in which jobs need to be processed through a (shared) network of machines. The network is given in the form of a graph the edges of which represent the machines. We are also given a set of jobs, each specified by its processing time and a path in the graph. Every job needs to be processed in the order of edges specified by its path. We assume that jobs can wait between machines and preemption is not allowed; that is, once a job is started being processed on a machine, it must be completed without interruption. Every machine can only process one job at a time. The makespan of a schedule is the earliest time by which all the jobs have finished processing. The flow time (a.k.a. the completion time) of a job in a schedule is the difference in time between when it finishes processing on its last machine and when the it begins processing on its first machine. The total flow time (or the sum of completion times) is the sum of flow times (or completion times) of all jobs. Our focus is on finding schedules with the minimum sum of completion times or minimum makespan. In this paper, we develop several algorithms (both approximate and exact) for the problem both on general graphs and when the underlying graph of machines is a tree. Even in the very special case when the underlying network is a simple star, the problem is very interesting as it models a biprocessor scheduling with applications to data migration.
Cite as

Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, and Yifeng Zhang. Scheduling Problems over Network of Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.APPROX-RANDOM.2017.5,
  author =	{Friggstad, Zachary and Golestanian, Arnoosh and Khodamoradi, Kamyar and Martin, Christopher and Rahgoshay, Mirmahdi and Rezapour, Mohsen and Salavatipour, Mohammad R. and Zhang, Yifeng},
  title =	{{Scheduling Problems over Network of Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.5},
  URN =		{urn:nbn:de:0030-drops-75547},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.5},
  annote =	{Keywords: approximation algorithms, job-shop scheduling, min-sum edge coloring, minimum latency}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.55
Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs

Authors: Sara Ahmadian and Zachary Friggstad

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We pursue a study of the Generalized Demand Matching problem, a common generalization of the b-Matching and Knapsack problems. Here, we are given a graph with vertex capacities, edge profits, and asymmetric demands on the edges. The goal is to find a maximum-profit subset of edges so the demands of chosen edges do not violate the vertex capacities. This problem is APX-hard and constant-factor approximations are already known. Our main results fall into two categories. First, using iterated relaxation and various filtering strategies, we show with an efficient rounding algorithm that if an additional matroid structure M is given and we further only allow sets that are independent in M, the natural LP relaxation has an integrality gap of at most 25/3. This can be further improved in various special cases, for example we improve over the 15-approximation for the previously- studied Coupled Placement problem [Korupolu et al. 2014] by giving a 7-approximation. Using similar techniques, we show the problem of computing a minimum-cost base in M satisfying vertex capacities admits a (1,3)-bicriteria approximation: the cost is at most the optimum and the capacities are violated by a factor of at most 3. This improves over the previous (1,4)-approximation in the special case that M is the graphic matroid over the given graph [Fukanaga and Nagamochi, 2009]. Second, we show Demand Matching admits a polynomial-time approximation scheme in graphs that exclude a fixed minor. If all demands are polynomially-bounded integers, this is somewhat easy using dynamic programming in bounded-treewidth graphs. Our main technical contribution is a sparsification lemma that allows us to scale the demands of some items to be used in a more intricate dynamic programming algorithm, followed by some randomized rounding to filter our scaled-demand solution to one whose original demands satisfy all constraints.
Cite as

Sara Ahmadian and Zachary Friggstad. Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ahmadian_et_al:LIPIcs.ICALP.2017.55,
  author =	{Ahmadian, Sara and Friggstad, Zachary},
  title =	{{Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.55},
  URN =		{urn:nbn:de:0030-drops-74600},
  doi =		{10.4230/LIPIcs.ICALP.2017.55},
  annote =	{Keywords: Approximation Algorithms, Column-Restricted Packing, Demand Matching, Matroids, Planar Graphs}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.75
Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median

Authors: Zachary Friggstad and Yifeng Zhang

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

Abstract
Budgeted Red-Blue Median is a generalization of classic k-Median in that there are two sets of facilities, say R and B, that can be used to serve clients located in some metric space. The goal is to open kr facilities in R and kb facilities in B for some given bounds kr, kb and connect each client to their nearest open facility in a way that minimizes the total connection cost. We extend work by Hajiaghayi, Khandekar, and Kortsarz [2012] and show that a multipleswap local search heuristic can be used to obtain a (5 + epsilon)-approximation for Budgeted RedBlue Median for any constant epsilon > 0. This is an improvement over their single swap analysis and beats the previous best approximation guarantee of 8 by Swamy [2014]. We also present a matching lower bound showing that for every p >= 1, there are instances of Budgeted Red-Blue Median with local optimum solutions for the p-swap heuristic whose cost is 5 + Omega(1/p) times the optimum solution cost. Thus, our analysis is tight up to the lower order terms. In particular, for any epsilon > 0 we show the single-swap heuristic admits local optima whose cost can be as bad as 7 - epsilon times the optimum solution cost.
Cite as

Zachary Friggstad and Yifeng Zhang. Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ICALP.2016.75,
  author =	{Friggstad, Zachary and Zhang, Yifeng},
  title =	{{Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{75:1--75:13},
  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.75},
  URN =		{urn:nbn:de:0030-drops-62094},
  doi =		{10.4230/LIPIcs.ICALP.2016.75},
  annote =	{Keywords: Approximation Algorithms, Local search, Red-Blue Meidan}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.1
Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding

Authors: Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We consider a lower- and upper-bounded generalization of the classical facility location problem, where each facility has a capacity (upper bound) that limits the number of clients it can serve and a lower bound on the number of clients it must serve if it is opened. We develop an LP rounding framework that exploits a Voronoi diagram-based clustering approach to derive the first bicriteria constant approximation algorithm for this problem with non-uniform lower bounds and uniform upper bounds. This naturally leads to the the first LP-based approximation algorithm for the lower bounded facility location problem (with non-uniform lower bounds). We also demonstrate the versatility of our framework by extending this and presenting the first constant approximation algorithm for some connected variant of the problems in which the facilities are required to be connected as well.
Cite as

Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.SWAT.2016.1,
  author =	{Friggstad, Zachary and Rezapour, Mohsen and Salavatipour, Mohammad R.},
  title =	{{Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.1},
  URN =		{urn:nbn:de:0030-drops-60302},
  doi =		{10.4230/LIPIcs.SWAT.2016.1},
  annote =	{Keywords: Facility Location, Approximation Algorithm, LP Rounding}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.3
A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs

Authors: Zachary Friggstad, Jochen Könemann, and Mohammad Shadravan

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We demonstrate that the integrality gap of the natural cut-based LP relaxation for the directed Steiner tree problem is O(log k) in quasi-bipartite graphs with k terminals. Such instances can be seen to generalize set cover, so the integrality gap analysis is tight up to a constant factor. A novel aspect of our approach is that we use the primal-dual method; a technique that is rarely used in designing approximation algorithms for network design problems in directed graphs.
Cite as

Zachary Friggstad, Jochen Könemann, and Mohammad Shadravan. A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.SWAT.2016.3,
  author =	{Friggstad, Zachary and K\"{o}nemann, Jochen and Shadravan, Mohammad},
  title =	{{A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{3:1--3:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.3},
  URN =		{urn:nbn:de:0030-drops-60323},
  doi =		{10.4230/LIPIcs.SWAT.2016.3},
  annote =	{Keywords: Approximation algorithm, Primal-Dual algorithm, Directed Steiner tree}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.265
On Linear Programming Relaxations for Unsplittable Flow in Trees

Authors: Zachary Friggstad and Zhihan Gao

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

Abstract
We study some linear programming relaxations for the Unsplittable Flow problem on trees (UFP-Tree). Inspired by results obtained by Chekuri, Ene, and Korula for Unsplittable Flow on paths (UFP-Path), we present a relaxation with polynomially many constraints that has an integrality gap bound of O(log n * min(log m, log n)) where n denotes the number of tasks and m denotes the number of edges in the tree. This matches the approximation guarantee of their combinatorial algorithm and is the first demonstration of an efficiently-solvable relaxation for UFP-Tree with a sub-linear integrality gap. The new constraints in our LP relaxation are just a few of the (exponentially many) rank constraints that can be added to strengthen the natural relaxation. A side effect of how we prove our upper bound is an efficient O(1)-approximation for solving the rank LP. We also show that our techniques can be used to prove integrality gap bounds for similar LP relaxations for packing demand-weighted subtrees of an edge-capacitated tree. On the other hand, we show that the inclusion of all rank constraints does not reduce the integrality gap for UFP-Tree to a constant. Specifically, we show the integrality gap is Omega(sqrt(log n)) even in cases where all tasks share a common endpoint. In contrast, intersecting instances of UFP-Path are known to have an integrality gap of O(1) even if just a few of the rank 1 constraints are included. We also observe that applying two rounds of the Lovász-Schrijver SDP procedure to the natural LP for UFP-Tree derives an SDP whose integrality gap is also O(log n * min(log m, log n)).
Cite as

Zachary Friggstad and Zhihan Gao. On Linear Programming Relaxations for Unsplittable Flow in Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 265-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.APPROX-RANDOM.2015.265,
  author =	{Friggstad, Zachary and Gao, Zhihan},
  title =	{{On Linear Programming Relaxations for Unsplittable Flow in Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{265--283},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.265},
  URN =		{urn:nbn:de:0030-drops-53073},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.265},
  annote =	{Keywords: Unsplittable flow, Linear programming relaxation, Approximation algorithm}
}
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}
}
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 About DROPS Imprint Privacy Contact