Search Results

Documents authored by Kolliopoulos, Stavros G.

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.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
DOI: 10.4230/LIPIcs.STACS.2015.568
Extended Formulation Lower Bounds via Hypergraph Coloring?

Authors: Stavros G. Kolliopoulos and Yannis Moysoglou

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Exploring the power of linear programming for combinatorial optimization problems has been recently receiving renewed attention after a series of breakthrough impossibility results. From an algorithmic perspective, the related questions concern whether there are compact formulations even for problems that are known to admit polynomial-time algorithms. We propose a framework for proving lower bounds on the size of extended formulations. We do so by introducing a specific type of extended relaxations that we call product relaxations and is motivated by the study of the Sherali-Adams (SA) hierarchy. Then we show that for every approximate extended formulation of a polytope P, there is a product relaxation that has the same size and is at least as strong. We provide a methodology for proving lower bounds on the size of approximate product relaxations by lower bounding the chromatic number of an underlying hypergraph, whose vertices correspond to gap-inducing vectors. We extend the definition of product relaxations and our methodology to mixed integer sets. However in this case we are able to show that mixed product relaxations are at least as powerful as a special family of extended formulations. As an application of our method we show an exponential lower bound on the size of approximate mixed product relaxations for the metric capacitated facility location problem Cfl, a problem which seems to be intractable for linear programming as far as constant-gap compact formulations are concerned. Our lower bound implies an unbounded integrality gap for Cfl at Theta({N}) levels of the universal SA hierarchy which is independent of the starting relaxation; we only require that the starting relaxation has size 2^o(N), where N is the number of facilities in the instance. This proof yields the first such tradeoff for an SA procedure that is independent of the initial relaxation.
Cite as

Stavros G. Kolliopoulos and Yannis Moysoglou. Extended Formulation Lower Bounds via Hypergraph Coloring?. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 568-581, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kolliopoulos_et_al:LIPIcs.STACS.2015.568,
  author =	{Kolliopoulos, Stavros G. and Moysoglou, Yannis},
  title =	{{Extended Formulation Lower Bounds via Hypergraph Coloring?}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{568--581},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.568},
  URN =		{urn:nbn:de:0030-drops-49429},
  doi =		{10.4230/LIPIcs.STACS.2015.568},
  annote =	{Keywords: linear programming, extended formulations, inapproximability, facility location}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.297
Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location

Authors: Stavros G. Kolliopoulos and Yannis Moysoglou

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

Abstract
Metric facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. The capacity-constrained generalizations, such as capacitated facility location (CFL) and lower-bounded facility location (LBFL), have proved notorious as far as LP-based approximation is concerned: while there are local-search-based constant-factor approximations, there is no known linear relaxation with constant integrality gap. According to Williamson and Shmoys devising a relaxation-based approximation for CFL is among the top 10 open problems in approximation algorithms. This paper advances significantly the state-of-the-art on the effectiveness of linear programming for capacity-constrained facility location through a host of impossibility results for both CFL and LBFL. We show that the relaxations obtained from the natural LP at Omega(n) levels of the Sherali-Adams hierarchy have an unbounded gap, partially answering an open question from the literature. Here, n denotes the number of facilities in the instance. Building on the ideas for this result, we prove that the standard CFL relaxation enriched with the generalized flow-cover valid inequalities has also an unbounded gap. This disproves a long-standing conjecture of Levi et al. We finally introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation and captures general configuration-style LPs. We characterize the behavior of proper relaxations for CFL and LBFL through a sharp threshold phenomenon.
Cite as

Stavros G. Kolliopoulos and Yannis Moysoglou. Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 297-312, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kolliopoulos_et_al:LIPIcs.APPROX-RANDOM.2014.297,
  author =	{Kolliopoulos, Stavros G. and Moysoglou, Yannis},
  title =	{{Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{297--312},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.297},
  URN =		{urn:nbn:de:0030-drops-47046},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.297},
  annote =	{Keywords: Approximation Algorithms, Linear Programming, Facility Location}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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