2 Search Results for "Chan, Siu On"

Document
DOI: 10.4230/LIPIcs.ISAAC.2020.21
Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem

Authors: Kangsan Kim, Yongho Shin, and Hyung-Chan An

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

Abstract
Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement - odd, even, or unconstrained - of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse T-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound.
Cite as

Kangsan Kim, Yongho Shin, and Hyung-Chan An. Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.ISAAC.2020.21,
  author =	{Kim, Kangsan and Shin, Yongho and An, Hyung-Chan},
  title =	{{Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{21:1--21: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.21},
  URN =		{urn:nbn:de:0030-drops-133652},
  doi =		{10.4230/LIPIcs.ISAAC.2020.21},
  annote =	{Keywords: Facility location problems, approximation algorithms, clustering problems, parity constraints}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.41
Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy

Authors: Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, and Avner Magen

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
We give the first tight integrality gap for Vertex Cover in the Sherali-Adams SDP system. More precisely, we show that for every \epsilon >0, the standard SDP for Vertex Cover that is strengthened with the level-6 Sherali-Adams system has integrality gap 2-\epsilon. To the best of our knowledge this is the first nontrivial tight integrality gap for the Sherali-Adams SDP hierarchy for a combinatorial problem with hard constraints. For our proof we introduce a new tool to establish Local-Global Discrepancy which uses simple facts from high-dimensional geometry. This allows us to give Sherali-Adams solutions with objective value n(1/2+o(1)) for graphs with small (2+o(1)) vector chromatic number. Since such graphs with no linear size independent sets exist, this immediately gives a tight integrality gap for the Sherali-Adams system for superconstant number of tightenings. In order to obtain a Sherali-Adams solution that also satisfies semidefinite conditions, we reduce semidefiniteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is valid for superconstant level Sherali-Adams SDPs.
Cite as

Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, and Avner Magen. Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 41-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{benabbas_et_al:LIPIcs.FSTTCS.2011.41,
  author =	{Benabbas, Siavosh and Chan, Siu On and Georgiou, Konstantinos and Magen, Avner},
  title =	{{Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{41--54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.41},
  URN =		{urn:nbn:de:0030-drops-33299},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.41},
  annote =	{Keywords: Vertex Cover, Integrality Gap, Lift-and-Project systems, Linear Programming, Semidefinite Programming}
}
  • Refine by Author
  • 1 An, Hyung-Chan
  • 1 Benabbas, Siavosh
  • 1 Chan, Siu On
  • 1 Georgiou, Konstantinos
  • 1 Kim, Kangsan
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Facility location and clustering

  • Refine by Keyword
  • 1 Facility location problems
  • 1 Integrality Gap
  • 1 Lift-and-Project systems
  • 1 Linear Programming
  • 1 Semidefinite Programming
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 1 2020

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