19 Search Results for "Friggstad, Zachary"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.52
Simultaneously Approximating All 𝓁_p-Norms in Correlation Clustering

Authors: Sami Davies, Benjamin Moseley, and Heather Newman

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
This paper considers correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously O(1)-approximate for all 𝓁_p-norms of the disagreement vector; in other words, a combinatorial O(1)-approximation of the all-norms objective for correlation clustering. This is the first proof that minimal sacrifice is needed in order to optimize different norms of the disagreement vector. In addition, our algorithm is the first combinatorial approximation algorithm for the 𝓁₂-norm objective, and more generally the first combinatorial algorithm for the 𝓁_p-norm objective when 1 < p < ∞. It is also faster than all previous algorithms that minimize the 𝓁_p-norm of the disagreement vector, with run-time O(n^ω), where O(n^ω) is the time for matrix multiplication on n × n matrices. When the maximum positive degree in the graph is at most Δ, this can be improved to a run-time of O(nΔ² log n).
Cite as

Sami Davies, Benjamin Moseley, and Heather Newman. Simultaneously Approximating All 𝓁_p-Norms in Correlation Clustering. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.ICALP.2024.52,
  author =	{Davies, Sami and Moseley, Benjamin and Newman, Heather},
  title =	{{Simultaneously Approximating All 𝓁\underlinep-Norms in Correlation Clustering}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{52:1--52:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.52},
  URN =		{urn:nbn:de:0030-drops-201950},
  doi =		{10.4230/LIPIcs.ICALP.2024.52},
  annote =	{Keywords: Approximation algorithms, correlation clustering, all-norms, lp-norms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.88
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints

Authors: Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In the MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k-assignment) such that the number of clauses satisfied by β is maximized. Maximum Coverage can be seen as a special case of CC-MaxSat, where the formula Φ is monotone, i.e., does not contain any negative literals. CC-MaxSat and Maximum Coverage are extremely well-studied problems in the approximation algorithms as well as the parameterized complexity literature. Our first conceptual contribution is that CC-MaxSat and Maximum Coverage are equivalent to each other in the context of FPT-Approximation parameterized by k (here, the approximation is in terms of the number of clauses satisfied/elements covered). In particular, we give a randomized reduction from CC-MaxSat to Maximum Coverage running in time 𝒪(1/ε)^{k} ⋅ (m+n)^{𝒪(1)} that preserves the approximation guarantee up to a factor of (1-ε). Furthermore, this reduction also works in the presence of "fairness" constraints on the satisfied clauses, as well as matroid constraints on the set of variables that are assigned true. Here, the "fairness" constraints are modeled by partitioning the clauses of the formula Φ into r different colors, and the goal is to find an assignment that satisfies at least t_j clauses of each color 1 ≤ j ≤ r. Armed with this reduction, we focus on designing FPT-Approximation schemes (FPT-ASes) for Maximum Coverage and its generalizations. Our algorithms are based on a novel combination of a variety of ideas, including a carefully designed probability distribution that exploits sparse coverage functions. These algorithms substantially generalize the results in Jain et al. [SODA 2023] for CC-MaxSat and Maximum Coverage for K_{d,d}-free set systems (i.e., no d sets share d elements), as well as a recent FPT-AS for Matroid Constrained Maximum Coverage by Sellier [ESA 2023] for frequency-d set systems.
Cite as

Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 88:1-88:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{inamdar_et_al:LIPIcs.ICALP.2024.88,
  author =	{Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Sahu, Abhishek and Saurabh, Saket and Upasana, Anannya},
  title =	{{Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{88:1--88:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.88},
  URN =		{urn:nbn:de:0030-drops-202318},
  doi =		{10.4230/LIPIcs.ICALP.2024.88},
  annote =	{Keywords: Partial Vertex Cover, Max SAT, FPT Approximation, Matroids}
}
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
DOI: 10.4230/LIPIcs.SWAT.2024.40
Approximation Algorithms for the Airport and Railway Problem

Authors: Mohammad R. Salavatipour and Lijiangnan Tian

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

Abstract
In this paper, we present approximation algorithms for the airport and railway problem (AR) on several classes of graphs. The AR problem, introduced by [Anna Adamaszek et al., 2016], is a combination of the Capacitated Facility Location problem (CFL) and the network design problem. An AR instance consists of a set of points (cities) V in a metric d(.,.), each of which is associated with a non-negative cost f_v and a number k, which represent respectively the cost of establishing an airport (facility) in the corresponding point, and the universal airport capacity. A feasible solution is a network of airports and railways providing services to all cities without violating any capacity, where railways are edges connecting pairs of points, with their costs equivalent to the distance between the respective points. The objective is to find such a network with the least cost. In other words, find a forest, each component having at most k points and one open facility, minimizing the total cost of edges and airport opening costs. Adamaszek et al. [Anna Adamaszek et al., 2016] presented a PTAS for AR in the two-dimensional Euclidean metric ℝ² with a uniform opening cost. In subsequent work [Anna Adamaszek et al., 2018] presented a bicriteria 4/3 (2+1/α)-approximation algorithm for AR with non-uniform opening costs but violating the airport capacity by a factor of 1+α, i.e. (1+α)k capacity where 0 < α ≤ 1, a (2+k/(k-1)+ε)-approximation algorithm and a bicriteria Quasi-Polynomial Time Approximation Scheme (QPTAS) for the same problem in the Euclidean plane ℝ². In this work, we give a 2-approximation for AR with a uniform opening cost for general metrics and an O(log n)-approximation for non-uniform opening costs. We also give a QPTAS for AR with a uniform opening cost in graphs of bounded treewidth and a QPTAS for a slightly relaxed version in the non-uniform setting. The latter implies O(1)-approximation on graphs of bounded doubling dimensions, graphs of bounded highway dimensions and planar graphs in quasi-polynomial time.
Cite as

Mohammad R. Salavatipour and Lijiangnan Tian. Approximation Algorithms for the Airport and Railway Problem. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{salavatipour_et_al:LIPIcs.SWAT.2024.40,
  author =	{Salavatipour, Mohammad R. and Tian, Lijiangnan},
  title =	{{Approximation Algorithms for the Airport and Railway Problem}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{40:1--40:16},
  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.40},
  URN =		{urn:nbn:de:0030-drops-200806},
  doi =		{10.4230/LIPIcs.SWAT.2024.40},
  annote =	{Keywords: Facility Location, Approximation Algorithms, Dynamic 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.ISAAC.2020.10
Approximation Algorithms for Generalized Path Scheduling

Authors: Haozhou Pang and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Scheduling problems where the machines can be represented as the edges of a network and each job needs to be processed by a sequence of machines that form a path in this network have been the subject of many research articles (e.g. flow shop is the special case where the network as well as the sequence of machines for each job is a simple path). In this paper we consider one such problem, called Generalized Path Scheduling (GPS) problem, which can be defined as follows. Given a set of non-preemptive jobs J and identical machines M ( |J| = n and |M| = m ). The machines are ordered on a path. Each job j = {P_j = {l_j, r_j}, p_j} is defined by its processing time p_j and a sub-path P_j from machine with index l_j to r_j (l_j, r_j ∈ M, and l_j ≤ r_j) specifying the order of machines it must go through. We assume each machine has a queue of infinite size where jobs can sit in the queue to resolve conflicts. Two objective functions, makespan and total completion time, are considered. Machines can be identical or unrelated. In the latter case, this problem generalizes the classical Flow shop problem (in which all jobs have to go through all machines from 1 to m in that order). Generalized Path Scheduling has been studied (e.g. see [Ronald Koch et al., 2009; Zachary Friggstad et al., 2019]). In this paper, we present several improved approximation algorithms for both objectives. For the case of number of machines being sub-logarithmic in the number of jobs we present a PTAS for both makespan and total completion time. The PTAS holds even on unrelated machines setting and therefore, generalizes the result of Hall [Leslie A. Hall, 1998] for the classic problem of Flow shop. For the case of identical machines, we present an O((log m)/(log log m))-approximation algorithms for both objectives, which improve the previous best result of [Zachary Friggstad et al., 2019]. We also show that the GPS problem is NP-complete for both makespan and total completion time objectives.
Cite as

Haozhou Pang and Mohammad R. Salavatipour. Approximation Algorithms for Generalized Path Scheduling. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{pang_et_al:LIPIcs.ISAAC.2020.10,
  author =	{Pang, Haozhou and Salavatipour, Mohammad R.},
  title =	{{Approximation Algorithms for Generalized Path Scheduling}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.10},
  URN =		{urn:nbn:de:0030-drops-133547},
  doi =		{10.4230/LIPIcs.ISAAC.2020.10},
  annote =	{Keywords: Approximation Algorithms, Path Scheduling, Flow shop, Job Shop}
}
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}
}
  • Refine by Author
  • 15 Friggstad, Zachary
  • 5 Salavatipour, Mohammad R.
  • 3 Mousavi, Ramin
  • 3 Swamy, Chaitanya
  • 2 Ahmadian, Sara
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Approximation algorithms analysis
  • 3 Theory of computation → Routing and network design problems
  • 2 Theory of computation → Scheduling algorithms
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Discrete optimization
  • Show More...

  • Refine by Keyword
  • 8 Approximation Algorithms
  • 5 approximation algorithms
  • 3 Directed Steiner tree
  • 2 Approximation algorithm
  • 2 Approximation algorithms
  • Show More...

  • Refine by Type
  • 19 document

  • Refine by Publication Year
  • 5 2024
  • 3 2016
  • 2 2017
  • 2 2020
  • 2 2022
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact