18 Search Results for "Salavatipour, Mohammad R."

Document
DOI: 10.4230/LIPIcs.ESA.2024.10
Sparse Outerstring Graphs Have Logarithmic Treewidth

Authors: Shinwoo An, Eunjin Oh, and Jie Xue

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with n vertices has treewidth O(αlog n), where α denotes the arboricity of the graph, with an almost matching lower bound of Ω(α log (n/α)). As a corollary, we show that a t-biclique-free outerstring graph has treewidth O(t(log t)log n). This leads to polynomial-time algorithms for most of the central NP-complete problems such as Independent Set, Vertex Cover, Dominating Set, Feedback Vertex Set, Coloring for sparse outerstring graphs. Also, we can obtain subexponential-time (exact, parameterized, and approximation) algorithms for various NP-complete problems such as Vertex Cover, Feedback Vertex Set and Cycle Packing for (not necessarily sparse) outerstring graphs.
Cite as

Shinwoo An, Eunjin Oh, and Jie Xue. Sparse Outerstring Graphs Have Logarithmic Treewidth. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ESA.2024.10,
  author =	{An, Shinwoo and Oh, Eunjin and Xue, Jie},
  title =	{{Sparse Outerstring Graphs Have Logarithmic Treewidth}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.10},
  URN =		{urn:nbn:de:0030-drops-210816},
  doi =		{10.4230/LIPIcs.ESA.2024.10},
  annote =	{Keywords: Outerstring graphs, geometric intersection graphs, treewidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.41
Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing

Authors: Chandra Chekuri and Rhea Jain

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [Chekuri et al., 2010; Guy Kortsarz and Zeev Nutov, 2011]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [Chekuri et al., 2010]. The rounding is based on recent results in hop-constrained oblivious routing [Ghaffari et al., 2021], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to h-hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of h-hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [Luis Gouveia and Markus Leitner, 2017; Gouveia et al., 2018; Arslan et al., 2020] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.
Cite as

Chandra Chekuri and Rhea Jain. Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 41:1-41:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.ESA.2024.41,
  author =	{Chekuri, Chandra and Jain, Rhea},
  title =	{{Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{41:1--41:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.41},
  URN =		{urn:nbn:de:0030-drops-211124},
  doi =		{10.4230/LIPIcs.ESA.2024.41},
  annote =	{Keywords: Buy-at-bulk, Hop-constrained network design, LP integrality gap, Fault-tolerant network design}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.48
Scheduling with Obligatory Tests

Authors: Konstantinos Dogeas, Thomas Erlebach, and Ya-Chun Liang

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations, a test and a processing part. The time required to execute the test is known in advance while the time required to execute the processing part becomes known only upon completion of the test. We use competitive analysis to study algorithms for minimizing the sum of completion times for n given jobs on a single machine. As our main result, we prove using a novel analysis technique that the natural 1-SORT algorithm has competitive ratio at most 1.861. For the special case of uniform test times, we show that a simple threshold-based algorithm has competitive ratio at most 1.585. We also prove a lower bound that shows that no deterministic algorithm can be better than √2-competitive even in the case of uniform test times.
Cite as

Konstantinos Dogeas, Thomas Erlebach, and Ya-Chun Liang. Scheduling with Obligatory Tests. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dogeas_et_al:LIPIcs.ESA.2024.48,
  author =	{Dogeas, Konstantinos and Erlebach, Thomas and Liang, Ya-Chun},
  title =	{{Scheduling with Obligatory Tests}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{48:1--48:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.48},
  URN =		{urn:nbn:de:0030-drops-211194},
  doi =		{10.4230/LIPIcs.ESA.2024.48},
  annote =	{Keywords: Competitive ratio, Online algorithm, Scheduling with testing, Sum of completion times}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.91
Euclidean Capacitated Vehicle Routing in the Random Setting: A 1.55-Approximation Algorithm

Authors: Zipei Nie and Hang Zhou

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We study the unit-demand capacitated vehicle routing problem in the random setting of the Euclidean plane. The objective is to visit n random terminals in a square using a set of tours of minimum total length, such that each tour visits the depot and at most k terminals. We design an algorithm combining the classical sweep heuristic and the framework for the Euclidean traveling salesman problem due to Arora [J. ACM 1998] and Mitchell [SICOMP 1999]. We show that our algorithm is a polynomial-time approximation of ratio at most 1.55 asymptotically almost surely. This improves on the prior ratio of 1.915 due to Mathieu and Zhou [RSA 2022]. In addition, we conjecture that, for any ε > 0, our algorithm is a (1+ε)-approximation asymptotically almost surely.
Cite as

Zipei Nie and Hang Zhou. Euclidean Capacitated Vehicle Routing in the Random Setting: A 1.55-Approximation Algorithm. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 91:1-91:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{nie_et_al:LIPIcs.ESA.2024.91,
  author =	{Nie, Zipei and Zhou, Hang},
  title =	{{Euclidean Capacitated Vehicle Routing in the Random Setting: A 1.55-Approximation Algorithm}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{91:1--91:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.91},
  URN =		{urn:nbn:de:0030-drops-211627},
  doi =		{10.4230/LIPIcs.ESA.2024.91},
  annote =	{Keywords: capacitated vehicle routing, approximation algorithm, combinatorial optimization}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.3
Degrees and Network Design: New Problems and Approximations

Authors: Michael Dinitz, Guy Kortsarz, and Shi Li

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

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

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

Copy BibTex To Clipboard

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

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi

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

Abstract
We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clustering problem, given a set P of points in ℝ^d, an integer k, and a non-negative real r, our objective is to position k closed balls of radius r to minimize the sum of distances from points not covered by the balls to their closest balls. Equivalently, we seek an optimal L₁-fitting of a union of k balls of radius r to a set of points in the Euclidean space. When r = 0, this corresponds to k-median; when the minimum sum is zero, indicating complete coverage of all points, it is k-center. Our primary result is a bicriteria approximation algorithm that, for a given ε > 0, produces a hybrid k-clustering with balls of radius (1+ε)r. This algorithm achieves a cost at most 1+ε of the optimum, and it operates in time 2^{(kd/ε)^𝒪(1)} ⋅ n^𝒪(1). Notably, considering the established lower bounds on k-center and k-median, our bicriteria approximation stands as the best possible result for Hybrid k-Clustering.
Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Hybrid k-Clustering: Blending k-Median and k-Center. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.APPROX/RANDOM.2024.4,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Hybrid k-Clustering: Blending k-Median and k-Center}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.4},
  URN =		{urn:nbn:de:0030-drops-209975},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.4},
  annote =	{Keywords: clustering, k-center, k-median, Euclidean space, fpt approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.25
Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound

Authors: Philip Cervenjak, Junhao Gan, Seeun William Umboh, and Anthony Wirth

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

Abstract
We consider the Max Unique Coverage problem, including applications to the data stream model. The input is a universe of n elements, a collection of m subsets of this universe, and a cardinality constraint, k. The goal is to select a subcollection of at most k sets that maximizes unique coverage, i.e, the number of elements contained in exactly one of the selected sets. The Max Unique Coverage problem has applications in wireless networks, radio broadcast, and envy-free pricing. Our first main result is a fixed-parameter tractable approximation scheme (FPT-AS) for Max Unique Coverage, parameterized by k and the maximum element frequency, r, which can be implemented on a data stream. Our FPT-AS finds a (1-ε)-approximation while maintaining a kernel of size Õ(k r/ε), which can be combined with subsampling to use Õ(k² r / ε³) space overall. This significantly improves on the previous-best FPT-AS with the same approximation, but a kernel of size Õ(k² r / ε²). In order to achieve our first result, we show upper bounds on the ratio of a collection’s coverage to the unique coverage of a maximizing subcollection; this is by constructing explicit algorithms that find a subcollection with unique coverage at least a logarithmic ratio of the collection’s coverage. We complement our algorithms with our second main result, showing that Ω(m / k²) space is necessary to achieve a (1.5 + o(1))/(ln k - 1)-approximation in the data stream. This dramatically improves the previous-best lower bound showing that Ω(m / k²) is necessary to achieve better than a e^{-1+1/k}-approximation.
Cite as

Philip Cervenjak, Junhao Gan, Seeun William Umboh, and Anthony Wirth. Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cervenjak_et_al:LIPIcs.APPROX/RANDOM.2024.25,
  author =	{Cervenjak, Philip and Gan, Junhao and Umboh, Seeun William and Wirth, Anthony},
  title =	{{Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.25},
  URN =		{urn:nbn:de:0030-drops-210183},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.25},
  annote =	{Keywords: Maximum unique coverage, maximum coverage, approximate kernel, data streams}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.84
Faster Approximation Schemes for (Constrained) k-Means with Outliers

Authors: Zhen Zhang, Junyu Huang, and Qilong Feng

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given a set of n points in ℝ^d and two positive integers k and m, the Euclidean k-means with outliers problem aims to remove at most m points, referred to as outliers, and minimize the k-means cost function for the remaining points. Developing algorithms for this problem remains an active area of research due to its prevalence in applications involving noisy data. In this paper, we give a (1+ε)-approximation algorithm that runs in n²d((k+m)ε^{-1})^O(kε^{-1}) time for the problem. When combined with a coreset construction method, the running time of the algorithm can be improved to be linear in n. For the case where k is a constant, this represents the first polynomial-time approximation scheme for the problem: Existing algorithms with the same approximation guarantee run in polynomial time only when both k and m are constants. Furthermore, our approach generalizes to variants of k-means with outliers incorporating additional constraints on instances, such as those related to capacities and fairness.
Cite as

Zhen Zhang, Junyu Huang, and Qilong Feng. Faster Approximation Schemes for (Constrained) k-Means with Outliers. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 84:1-84:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.MFCS.2024.84,
  author =	{Zhang, Zhen and Huang, Junyu and Feng, Qilong},
  title =	{{Faster Approximation Schemes for (Constrained) k-Means with Outliers}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{84:1--84:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.84},
  URN =		{urn:nbn:de:0030-drops-206408},
  doi =		{10.4230/LIPIcs.MFCS.2024.84},
  annote =	{Keywords: Approximation algorithms, clustering}
}
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
DOI: 10.4230/LIPIcs.ESA.2023.84
Approximation Schemes for Min-Sum k-Clustering

Authors: Ismail Naderi, Mohsen Rezapour, and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We consider the Min-Sum k-Clustering (k-MSC) problem. Given a set of points in a metric which is represented by an edge-weighted graph G = (V, E) and a parameter k, the goal is to partition the points V into k clusters such that the sum of distances between all pairs of the points within the same cluster is minimized. The k-MSC problem is known to be APX-hard on general metrics. The best known approximation algorithms for the problem obtained by Behsaz, Friggstad, Salavatipour and Sivakumar [Algorithmica 2019] achieve an approximation ratio of O(log |V|) in polynomial time for general metrics and an approximation ratio 2+ε in quasi-polynomial time for metrics with bounded doubling dimension. No approximation schemes for k-MSC (when k is part of the input) is known for any non-trivial metrics prior to our work. In fact, most of the previous works rely on the simple fact that there is a 2-approximate reduction from k-MSC to the balanced k-median problem and design approximation algorithms for the latter to obtain an approximation for k-MSC. In this paper, we obtain the first Quasi-Polynomial Time Approximation Schemes (QPTAS) for the problem on metrics induced by graphs of bounded treewidth, graphs of bounded highway dimension, graphs of bounded doubling dimensions (including fixed dimensional Euclidean metrics), and planar and minor-free graphs. We bypass the barrier of 2 for k-MSC by introducing a new clustering problem, which we call min-hub clustering, which is a generalization of balanced k-median and is a trade off between center-based clustering problems (such as balanced k-median) and pair-wise clustering (such as Min-Sum k-clustering). We then show how one can find approximation schemes for Min-hub clustering on certain classes of metrics.
Cite as

Ismail Naderi, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximation Schemes for Min-Sum k-Clustering. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{naderi_et_al:LIPIcs.ESA.2023.84,
  author =	{Naderi, Ismail and Rezapour, Mohsen and Salavatipour, Mohammad R.},
  title =	{{Approximation Schemes for Min-Sum k-Clustering}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{84:1--84:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.84},
  URN =		{urn:nbn:de:0030-drops-187379},
  doi =		{10.4230/LIPIcs.ESA.2023.84},
  annote =	{Keywords: Approximation Algorithms, Clustering, Dynamic Programming}
}
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
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.ISAAC.2020.11
Approximations for Throughput Maximization

Authors: Dylan Hyatt-Denesik, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour

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

Abstract
In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r_j, deadline d_j, and processing time p_j. They have to be scheduled non-preemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [r_j,d_j] window. This problem has been studied extensively (even for the case of m = 1). Several special cases of the problem remain open. Bar-Noy et al. [STOC1999] presented an algorithm with ratio 1-1/(1+1/m)^m for m machines, which approaches 1-1/e as m increases. For m = 1, Chuzhoy-Ostrovsky-Rabani [FOCS2001] presented an algorithm with approximation with ratio 1-1/e-ε (for any ε > 0). Recently Im-Li-Moseley [IPCO2017] presented an algorithm with ratio 1-1/e+ε₀ for some absolute constant ε₀ > 0 for any fixed m. They also presented an algorithm with ratio 1-O(√(log m/m))-ε for general m which approaches 1 as m grows. The approximability of the problem for m = O(1) remains a major open question. Even for the case of m = 1 and c = O(1) distinct processing times the problem is open (Sgall [ESA2012]). In this paper we study the case of m = O(1) and show that if there are c distinct processing times, i.e. p_j’s come from a set of size c, then there is a randomized (1-ε)-approximation that runs in time O(n^{mc⁷ε^(-6)}log T), where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning.
Cite as

Dylan Hyatt-Denesik, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour. Approximations for Throughput Maximization. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hyattdenesik_et_al:LIPIcs.ISAAC.2020.11,
  author =	{Hyatt-Denesik, Dylan and Rahgoshay, Mirmahdi and Salavatipour, Mohammad R.},
  title =	{{Approximations for Throughput Maximization}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{11:1--11:17},
  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.11},
  URN =		{urn:nbn:de:0030-drops-133555},
  doi =		{10.4230/LIPIcs.ISAAC.2020.11},
  annote =	{Keywords: Scheduling, Approximation Algorithms, Throughput Maximization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.33
Asymptotic Quasi-Polynomial Time Approximation Scheme for Resource Minimization for Fire Containment

Authors: Mirmahdi Rahgoshay and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P = NP [King and MacGillivray, 2010]. Chalermsook and Chuzhoy [Chalermsook and Chuzhoy, 2010] presented a Linear Programming based O(log^* n) approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili, Baggio, and Zenklusen [Adjiashvili et al., 2017] to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let ε>0, and ℐ be an instance of RMFC where the optimum number of firefighters to save all the leaves is OPT(ℐ). We present an algorithm which uses at most ⌈(1+ε)OPT(ℐ)⌉ many firefighters at each time step and runs in time n^O(log log n/ε). This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is O(log log n), not O(log n). Our result combines a more powerful height reduction lemma than the one in [Adjiashvili et al., 2017] with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in [Adjiashvili et al., 2017] plus a more careful analysis to improve their 12-approximation and provide a polynomial time (5+ε)-approximation.
Cite as

Mirmahdi Rahgoshay and Mohammad R. Salavatipour. Asymptotic Quasi-Polynomial Time Approximation Scheme for Resource Minimization for Fire Containment. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rahgoshay_et_al:LIPIcs.STACS.2020.33,
  author =	{Rahgoshay, Mirmahdi and Salavatipour, Mohammad R.},
  title =	{{Asymptotic Quasi-Polynomial Time Approximation Scheme for Resource Minimization for Fire Containment}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.33},
  URN =		{urn:nbn:de:0030-drops-118946},
  doi =		{10.4230/LIPIcs.STACS.2020.33},
  annote =	{Keywords: Firefighter Problem, Resource Management, Fire Containment, Approximation Algorithm, Asymptotic Approximation Scheme}
}
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}
}
  • Refine by Author
  • 9 Salavatipour, Mohammad R.
  • 4 Friggstad, Zachary
  • 3 Rahgoshay, Mirmahdi
  • 3 Rezapour, Mohsen
  • 1 Ahmadian, Sara
  • Show More...

  • Refine by Classification
  • 3 Theory of computation
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Facility location and clustering
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Routing and network design problems
  • Show More...

  • Refine by Keyword
  • 5 Approximation Algorithms
  • 2 Approximation Algorithm
  • 2 Clustering
  • 2 Dynamic Programming
  • 2 Facility Location
  • Show More...

  • Refine by Type
  • 18 document

  • Refine by Publication Year
  • 9 2024
  • 3 2020
  • 2 2016
  • 1 2014
  • 1 2017
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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