91 Search Results for "Megow, Nicole"

Volume

LIPIcs, Volume 275

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

APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA

Editors: Nicole Megow and Adam Smith

Document
DOI: 10.4230/DagRep.13.2.1
Scheduling (Dagstuhl Seminar 23061)

Authors: Nicole Megow, Benjamin J. Moseley, David Shmoys, Ola Svensson, Sergei Vassilvitskii, and Jens Schlöter

Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23061 "Scheduling". The seminar focused on the emerging models for beyond-worst case algorithm design, in particular, recent approaches that incorporate learning. This includes models for the integration of learning into algorithm design that have been proposed recently and that have already demonstrated advances in the state-of-art for various scheduling applications: (i) scheduling with error-prone learned predictions, (ii) data-driven algorithm design, and (iii) stochastic and Bayesian learning in scheduling.
Cite as

Nicole Megow, Benjamin J. Moseley, David Shmoys, Ola Svensson, Sergei Vassilvitskii, and Jens Schlöter. Scheduling (Dagstuhl Seminar 23061). In Dagstuhl Reports, Volume 13, Issue 2, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{megow_et_al:DagRep.13.2.1,
  author =	{Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens},
  title =	{{Scheduling (Dagstuhl Seminar 23061)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{2},
  editor =	{Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.2.1},
  URN =		{urn:nbn:de:0030-drops-191789},
  doi =		{10.4230/DagRep.13.2.1},
  annote =	{Keywords: scheduling, mathematical optimization, approximation algorithms, learning methods, uncertainty}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023
LIPIcs, Volume 275, APPROX/RANDOM 2023, Complete Volume

Authors: Nicole Megow and Adam Smith

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

Abstract
LIPIcs, Volume 275, APPROX/RANDOM 2023, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 1-1304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{megow_et_al:LIPIcs.APPROX/RANDOM.2023,
  title =	{{LIPIcs, Volume 275, APPROX/RANDOM 2023, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{1--1304},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023},
  URN =		{urn:nbn:de:0030-drops-188246},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023},
  annote =	{Keywords: LIPIcs, Volume 275, APPROX/RANDOM 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Nicole Megow and Adam Smith

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 0:i-0:xxiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{megow_et_al:LIPIcs.APPROX/RANDOM.2023.0,
  author =	{Megow, Nicole and Smith, Adam},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{0:i--0:xxiv},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.0},
  URN =		{urn:nbn:de:0030-drops-188254},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.1
On Complexity of 1-Center in Various Metrics

Authors: Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., and Saeed Seddighin

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

Abstract
We consider the classic 1-center problem: Given a set P of n points in a metric space find the point in P that minimizes the maximum distance to the other points of P. We study the complexity of this problem in d-dimensional 𝓁_p-metrics and in edit and Ulam metrics over strings of length d. Our results for the 1-center problem may be classified based on d as follows. - Small d. Assuming the hitting set conjecture (HSC), we show that when d = ω(log n), no subquadratic algorithm can solve the 1-center problem in any of the 𝓁_p-metrics, or in the edit or Ulam metrics. - Large d. When d = Ω(n), we extend our conditional lower bound to rule out subquartic algorithms for the 1-center problem in edit metric (assuming Quantified SETH). On the other hand, we give a (1+ε)-approximation for 1-center in the Ulam metric with running time O_{ε}̃(nd+n²√d). We also strengthen some of the above lower bounds by allowing approximation algorithms or by reducing the dimension d, but only against a weaker class of algorithms which list all requisite solutions. Moreover, we extend one of our hardness results to rule out subquartic algorithms for the well-studied 1-median problem in the edit metric, where given a set of n strings each of length n, the goal is to find a string in the set that minimizes the sum of the edit distances to the rest of the strings in the set.
Cite as

Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., and Saeed Seddighin. On Complexity of 1-Center in Various Metrics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.APPROX/RANDOM.2023.1,
  author =	{Abboud, Amir and Bateni, MohammadHossein and Cohen-Addad, Vincent and Karthik C. S. and Seddighin, Saeed},
  title =	{{On Complexity of 1-Center in Various Metrics}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{1:1--1:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.1},
  URN =		{urn:nbn:de:0030-drops-188260},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.1},
  annote =	{Keywords: Center, Clustering, Edit metric, Ulam metric, Hamming metric, Fine-grained Complexity, Approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.2
Probabilistic Metric Embedding via Metric Labeling

Authors: Kamesh Munagala, Govind S. Sankar, and Erin Taylor

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

Abstract
We consider probabilistic embedding of metric spaces into ultra-metrics (or equivalently to a constant factor, into hierarchically separated trees) to minimize the expected distortion of any pairwise distance. Such embeddings have been widely used in network design and online algorithms. Our main result is a polynomial time algorithm that approximates the optimal distortion on any instance to within a constant factor. We achieve this via a novel LP formulation that reduces this problem to a probabilistic version of uniform metric labeling.
Cite as

Kamesh Munagala, Govind S. Sankar, and Erin Taylor. Probabilistic Metric Embedding via Metric Labeling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{munagala_et_al:LIPIcs.APPROX/RANDOM.2023.2,
  author =	{Munagala, Kamesh and Sankar, Govind S. and Taylor, Erin},
  title =	{{Probabilistic Metric Embedding via Metric Labeling}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{2:1--2:10},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.2},
  URN =		{urn:nbn:de:0030-drops-188279},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.2},
  annote =	{Keywords: Metric Embedding, Approximation Algorithms, Ultrametrics}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.3
Approximating Submodular k-Partition via Principal Partition Sequence

Authors: Karthekeyan Chandrasekaran and Weihang Wang

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

Abstract
In submodular k-partition, the input is a submodular function f:2^V → ℝ_{≥ 0} (given by an evaluation oracle) along with a positive integer k and the goal is to find a partition of the ground set V into k non-empty parts V_1, V_2, …, V_k in order to minimize ∑_{i=1}^k f(V_i). Narayanan, Roy, and Patkar [Narayanan et al., 1996] designed an algorithm for submodular k-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is 2 for the special case of graph cut functions (which was subsequently rediscovered by Ravi and Sinha [R. Ravi and A. Sinha, 2008]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions - namely monotone, symmetric, and posimodular and show the following results: 1) The approximation factor of their algorithm for monotone submodular k-partition is 4/3. This result improves on the 2-factor that was known to be achievable for monotone submodular k-partition via other algorithms. Moreover, our upper bound of 4/3 matches the recently shown lower bound under polynomial number of function evaluation queries [Santiago, 2021]. Our upper bound of 4/3 is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular k-partition. 2) The approximation factor of their algorithm for symmetric submodular k-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. 3) The approximation factor of their algorithm for posimodular submodular k-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is Ω(n/k).
Cite as

Karthekeyan Chandrasekaran and Weihang Wang. Approximating Submodular k-Partition via Principal Partition Sequence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.APPROX/RANDOM.2023.3,
  author =	{Chandrasekaran, Karthekeyan and Wang, Weihang},
  title =	{{Approximating Submodular k-Partition via Principal Partition Sequence}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{3:1--3:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.3},
  URN =		{urn:nbn:de:0030-drops-188284},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.3},
  annote =	{Keywords: Approximation algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.4
Experimental Design for Any p-Norm

Authors: Lap Chi Lau, Robert Wang, and Hong Zhou

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

Abstract
We consider a general p-norm objective for experimental design problems that captures some well-studied objectives (D/A/E-design) as special cases. We prove that a randomized local search approach provides a unified algorithm to solve this problem for all nonnegative integer p. This provides the first approximation algorithm for the general p-norm objective, and a nice interpolation of the best known bounds of the special cases.
Cite as

Lap Chi Lau, Robert Wang, and Hong Zhou. Experimental Design for Any p-Norm. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lau_et_al:LIPIcs.APPROX/RANDOM.2023.4,
  author =	{Lau, Lap Chi and Wang, Robert and Zhou, Hong},
  title =	{{Experimental Design for Any p-Norm}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{4:1--4:21},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.4},
  URN =		{urn:nbn:de:0030-drops-188292},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.4},
  annote =	{Keywords: Approximation Algorithm, Optimal Experimental Design, Randomized Local Search}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.5
Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines

Authors: George Karakostas and Stavros G. Kolliopoulos

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

Abstract
We study the classic weighted maximum throughput problem on unrelated machines. We give a (1-1/e-ε)-approximation algorithm for the preemptive case. To our knowledge this is the first ever approximation result for this problem. It is an immediate consequence of a polynomial-time reduction we design, that uses any ρ-approximation algorithm for the single-machine problem to obtain an approximation factor of (1-1/e)ρ -ε for the corresponding unrelated-machines problem, for any ε > 0. On a single machine we present a PTAS for the non-preemptive version of the problem for the special case of a constant number of distinct due dates or distinct release dates. By our reduction this yields an approximation factor of (1-1/e) -ε for the non-preemptive problem on unrelated machines when there is a constant number of distinct due dates or release dates on each machine.
Cite as

George Karakostas and Stavros G. Kolliopoulos. Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{karakostas_et_al:LIPIcs.APPROX/RANDOM.2023.5,
  author =	{Karakostas, George and Kolliopoulos, Stavros G.},
  title =	{{Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{5:1--5:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.5},
  URN =		{urn:nbn:de:0030-drops-188305},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.5},
  annote =	{Keywords: scheduling, maximum weighted throughput, unrelated machines, approximation algorithm, PTAS}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.6
Facility Location in the Sublinear Geometric Model

Authors: Morteza Monemizadeh

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

Abstract
In the sublinear geometric model, we are provided with an oracle access to a point set P of n points in a bounded discrete space [Δ]², where Δ = n^O(1) is a polynomially bounded number in n. That is, we do not have direct access to the points, but we can make certain types of queries and there is an oracle that responds to our queries. The type of queries that we assume we can make in this paper, are range counting queries where ranges are axis-aligned rectangles (that are basic primitives in database [Srikanta Tirthapura and David P. Woodruff, 2012; Bentley, 1975; Mark de Berg et al., 2008], computational geometry [Pankaj K. Agarwal, 2004; Pankaj K. Agarwal et al., 1996; Boris Aronov et al., 2010; Boris Aronov et al., 2009], and machine learning [Menachem Sadigurschi and Uri Stemmer, 2021; Long and Tan, 1998; Michael J. Kearns and Umesh V. Vazirani, 1995; Michael J. Kearns and Umesh V. Vazirani, 1994]). The oracle then answers these queries by returning the number of points that are in queried ranges. Let {Alg} be an algorithm that (exactly or approximately) solves a problem 𝒫 in the sublinear geometric model. The query complexity of Alg is measured in terms of the number of queries that Alg makes to solve 𝒫. In this paper, we study the complexity of the (uniform) Euclidean facility location problem in the sublinear geometric model. We develop a randomized sublinear algorithm that with high probability, (1+ε)-approximates the cost of the Euclidean facility location problem of the point set P in the sublinear geometric model using Õ(√n) range counting queries. We complement this result by showing that approximating the cost of the Euclidean facility location problem within o(log(n))-factor in the sublinear geometric model using the sampling strategy that we propose for our sublinear algorithm needs Ω̃(n^{1/4}) RangeCount queries. We leave it as an open problem whether such a polynomial lower bound on the number of RangeCount queries exists for any randomized sublinear algorithm that approximates the cost of the facility location problem within a constant factor.
Cite as

Morteza Monemizadeh. Facility Location in the Sublinear Geometric Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{monemizadeh:LIPIcs.APPROX/RANDOM.2023.6,
  author =	{Monemizadeh, Morteza},
  title =	{{Facility Location in the Sublinear Geometric Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{6:1--6:24},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.6},
  URN =		{urn:nbn:de:0030-drops-188315},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.6},
  annote =	{Keywords: Facility Location, Sublinear Geometric Model, Range Counting Queries}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.7
Bicriteria Approximation Algorithms for Priority Matroid Median

Authors: Tanvi Bajpai and Chandra Chekuri

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

Abstract
Fairness considerations have motivated new clustering problems and algorithms in recent years. In this paper we consider the Priority Matroid Median problem which generalizes the Priority k-Median problem that has recently been studied. The input consists of a set of facilities ℱ and a set of clients 𝒞 that lie in a metric space (ℱ ∪ 𝒞,d), and a matroid ℳ = (ℱ,ℐ) over the facilities. In addition, each client j has a specified radius r_j ≥ 0 and each facility i ∈ ℱ has an opening cost f_i > 0. The goal is to choose a subset S ⊆ ℱ of facilities to minimize ∑_{i ∈ ℱ} f_i + ∑_{j ∈ 𝒞} d(j,S) subject to two constraints: (i) S is an independent set in ℳ (that is S ∈ ℐ) and (ii) for each client j, its distance to an open facility is at most r_j (that is, d(j,S) ≤ r_j). For this problem we describe the first bicriteria (c₁,c₂) approximations for fixed constants c₁,c₂: the radius constraints of the clients are violated by at most a factor of c₁ and the objective cost is at most c₂ times the optimum cost. We also improve the previously known bicriteria approximation for the uniform radius setting (r_j : = L ∀ j ∈ 𝒞).
Cite as

Tanvi Bajpai and Chandra Chekuri. Bicriteria Approximation Algorithms for Priority Matroid Median. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bajpai_et_al:LIPIcs.APPROX/RANDOM.2023.7,
  author =	{Bajpai, Tanvi and Chekuri, Chandra},
  title =	{{Bicriteria Approximation Algorithms for Priority Matroid Median}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{7:1--7:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.7},
  URN =		{urn:nbn:de:0030-drops-188328},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.7},
  annote =	{Keywords: k-median, fair clustering, matroid}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.8
Approximation Algorithms for Directed Weighted Spanners

Authors: Elena Grigorescu, Nithish Kumar, and Young-San Lin

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

Abstract
In the pairwise weighted spanner problem, the input consists of a weighted directed graph on n vertices, where each edge is assigned both a cost and a length. Furthermore, we are given k terminal vertex pairs and a distance constraint for each pair. The goal is to find a minimum-cost subgraph in which the distance constraints are satisfied. We study the weighted spanner problem, in which the edges have positive integral lengths of magnitudes that are polynomial in n, while the costs are arbitrary non-negative rational numbers. Our results include the following in the classical offline setting: - An Õ(n^{4/5 + ε})-approximation algorithm for the weighted pairwise spanner problem. When the edges have unit costs and lengths, the best previous algorithm gives an Õ(n^{3/5 + ε})-approximation, due to Chlamtáč, Dinitz, Kortsarz, and Laekhanukit (Transactions on Algorithms, 2020). - An Õ(n^{1/2+ε})-approximation algorithm for the weighted spanner problem when the terminal pairs consist of all vertex pairs and the distances must be preserved exactly. When the edges have unit costs and arbitrary positive lengths, the best previous algorithm gives an Õ(n^{1/2})-approximation for the all-pair spanner problem, due to Berman, Bhattacharyya, Makarychev, Raskhodnikova, and Yaroslavtsev (Information and Computation, 2013). We also prove the first results for the weighted spanners in the online setting. Our results include the following: - An Õ(k^{1/2 + ε})-competitive algorithm for the online weighted pairwise spanner problem. The state-of-the-art results are an Õ(n^{4/5})-competitive algorithm when edges have unit costs and arbitrary positive lengths, and a min{Õ(k^{1/2 + ε}), Õ(n^{2/3 + ε})}-competitive algorithm when edges have unit costs and lengths, due to Grigorescu, Lin, and Quanrud (APPROX, 2021). - An Õ(k^ε)-competitive algorithm for the online weighted single-source (or single-sink) spanner problem. Without distance constraints, this problem is equivalent to the online directed Steiner tree problem. The best previous algorithm for online directed Steiner trees is an Õ(k^ε)-competitive algorithm, due to Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP, 2018). Our online results also imply efficient approximation algorithms for the corresponding offline problems. To the best of our knowledge, these are the first approximation (online) polynomial-time algorithms with sublinear approximation (competitive) ratios for the weighted spanner problems.
Cite as

Elena Grigorescu, Nithish Kumar, and Young-San Lin. Approximation Algorithms for Directed Weighted Spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grigorescu_et_al:LIPIcs.APPROX/RANDOM.2023.8,
  author =	{Grigorescu, Elena and Kumar, Nithish and Lin, Young-San},
  title =	{{Approximation Algorithms for Directed Weighted Spanners}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{8:1--8:23},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.8},
  URN =		{urn:nbn:de:0030-drops-188335},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.8},
  annote =	{Keywords: directed weighted spanners, linear programming, junction tree}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.9
Approximation Algorithms and Lower Bounds for Graph Burning

Authors: Matej Lieskovský, Jiří Sgall, and Andreas Emil Feldmann

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

Abstract
Graph Burning models information spreading in a given graph as a process such that in each step one node is infected (informed) and also the infection spreads to all neighbors of previously infected nodes. Formally, given a graph G = (V,E), possibly with edge lengths, the burning number b(G) is the minimum number g such that there exist nodes v_0,…,v_{g-1} ∈ V satisfying the property that for each u ∈ V there exists i ∈ {0,…,g-1} so that the distance between u and v_i is at most i. We present a randomized 2.314-approximation algorithm for computing the burning number of a general graph, even with arbitrary edge lengths. We complement this by an approximation lower bound of 2 for the case of equal length edges, and a lower bound of 4/3 for the case when edges are restricted to have length 1. This improves on the previous 3-approximation algorithm and an APX-hardness result.
Cite as

Matej Lieskovský, Jiří Sgall, and Andreas Emil Feldmann. Approximation Algorithms and Lower Bounds for Graph Burning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lieskovsky_et_al:LIPIcs.APPROX/RANDOM.2023.9,
  author =	{Lieskovsk\'{y}, Matej and Sgall, Ji\v{r}{\'\i} and Feldmann, Andreas Emil},
  title =	{{Approximation Algorithms and Lower Bounds for Graph Burning}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{9:1--9:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.9},
  URN =		{urn:nbn:de:0030-drops-188345},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.9},
  annote =	{Keywords: Graph Algorithms, approximation Algorithms, randomized Algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.10
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems

Authors: Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz

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

Abstract
We study the question of when an approximate search optimization problem is harder than the associated decision problem. Specifically, we study a natural and quite general model of black-box search-to-decision reductions, which we call branch-and-bound reductions (in analogy with branch-and-bound algorithms). In this model, an algorithm attempts to minimize (or maximize) a function f: D → ℝ_{≥ 0} by making oracle queries to h_f : 𝒮 → ℝ_{≥ 0} satisfying min_{x ∈ S} f(x) ≤ h_f(S) ≤ γ ⋅ min_{x ∈ S} f(x) (*) for some γ ≥ 1 and any subset S in some allowed class of subsets 𝒮 of the domain D. (When the goal is to maximize f, h_f instead yields an approximation to the maximal value of f over S.) We show tight upper and lower bounds on the number of queries q needed to find even a γ'-approximate minimizer (or maximizer) for quite large γ' in a number of interesting settings, as follows. - For arbitrary functions f : {0,1}ⁿ → ℝ_{≥ 0}, where 𝒮 contains all subsets of the domain, we show that no branch-and-bound reduction can achieve γ' ≲ γ^{n/log q}, while a simple greedy approach achieves essentially γ^{n/log q}. - For a large class of MAX-CSPs, where 𝒮 := {S_w} contains each set of assignments to the variables induced by a partial assignment w, we show that no branch-and-bound reduction can do significantly better than essentially a random guess, even when the oracle h_f guarantees an approximation factor of γ ≈ 1+√{log(q)/n}. - For the Traveling Salesperson Problem (TSP), where 𝒮 := {S_p} contains each set of tours extending a path p, we show that no branch-and-bound reduction can achieve γ' ≲ (γ-1) n/log q. We also prove a nearly matching upper bound in our model. These results show an oracle model in which approximate search and decision are strongly separated. (In particular, our result for TSP can be viewed as a negative answer to a question posed by Bellare and Goldwasser (SIAM J. Comput. 1994), though only in an oracle model.) We also note two alternative interpretations of our results. First, if we view h_f as a data structure, then our results unconditionally rule out black-box search-to-decision reductions for certain data structure problems. Second, if we view h_f as an efficiently computable heuristic, then our results show that any reasonably efficient branch-and-bound algorithm requires more guarantees from its heuristic than simply Eq. (*). Behind our results is a "useless oracle lemma," which allows us to argue that under certain conditions the oracle h_f is "useless," and which might be of independent interest. See also the full version [Alexander Golovnev et al., 2022].
Cite as

Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz. The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{golovnev_et_al:LIPIcs.APPROX/RANDOM.2023.10,
  author =	{Golovnev, Alexander and Guo, Siyao and Peters, Spencer and Stephens-Davidowitz, Noah},
  title =	{{The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{10:1--10:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.10},
  URN =		{urn:nbn:de:0030-drops-188351},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.10},
  annote =	{Keywords: search-to-decision reductions, oracles, constraint satisfaction, traveling salesman, discrete optimization}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.11
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment

Authors: Eden Chlamtáč, Yury Makarychev, and Ali Vakilian

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

Abstract
We provide new approximation algorithms for the Red-Blue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for Red-Blue Set Cover achieves Õ(m^{1/3})-approximation improving on the Õ(m^{1/2})-approximation due to Elkin and Peleg (where m is the number of sets). Our approximation algorithm for MMSA_t (for circuits of depth t) gives an Õ(N^{1-δ}) approximation for δ = 1/32^{3-⌈t/2⌉}, where N is the number of gates and variables. No non-trivial approximation algorithms for MMSA_t with t ≥ 4 were previously known. We complement these results with lower bounds for these problems: For Red-Blue Set Cover, we provide a nearly approximation preserving reduction from Min k-Union that gives an ̃Ω(m^{1/4 - ε}) hardness under the Dense-vs-Random conjecture, while for MMSA we sketch a proof that an SDP relaxation strengthened by Sherali-Adams has an integrality gap of N^{1-ε} where ε → 0 as the circuit depth t → ∞.
Cite as

Eden Chlamtáč, Yury Makarychev, and Ali Vakilian. Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chlamtac_et_al:LIPIcs.APPROX/RANDOM.2023.11,
  author =	{Chlamt\'{a}\v{c}, Eden and Makarychev, Yury and Vakilian, Ali},
  title =	{{Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{11:1--11:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.11},
  URN =		{urn:nbn:de:0030-drops-188366},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.11},
  annote =	{Keywords: Red-Blue Set Cover Problem, Circuit Minimum Monotone Satisfying Assignment (MMSA) Problem, LP Rounding}
}
  • Refine by Author
  • 23 Megow, Nicole
  • 4 Hoeksma, Ruben
  • 4 Nölke, Lukas
  • 4 Simon, Bertrand
  • 3 Bansal, Nikhil
  • Show More...

  • Refine by Classification
  • 11 Theory of computation → Approximation algorithms analysis
  • 9 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 8 Theory of computation → Design and analysis of algorithms
  • 6 Theory of computation → Online algorithms
  • 5 Theory of computation
  • Show More...

  • Refine by Keyword
  • 12 approximation algorithms
  • 8 scheduling
  • 3 Approximation Algorithms
  • 3 approximation algorithm
  • 3 competitive analysis
  • Show More...

  • Refine by Type
  • 90 document
  • 1 volume

  • Refine by Publication Year
  • 71 2023
  • 5 2020
  • 3 2019
  • 2 2018
  • 2 2021
  • 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