4 Search Results for "Adamaszek, Michal"

Document
DOI: 10.4230/LIPIcs.ESA.2018.65
Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs

Authors: Michal Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We consider two optimization problems in planar graphs. In {Maximum Weight Independent Set of Objects} we are given a graph G and a family D of {objects}, each being a connected subgraph of G with a prescribed weight, and the task is to find a maximum-weight subfamily of D consisting of pairwise disjoint objects. In {Minimum Weight Distance Set Cover} we are given an edge-weighted graph G, two sets D,C of vertices of G, where vertices of D have prescribed weights, and a nonnegative radius r. The task is to find a minimum-weight subset of D such that every vertex of C is at distance at most r from some selected vertex. Via simple reductions, these two problems generalize a number of geometric optimization tasks, notably {Maximum Weight Independent Set} for polygons in the plane and {Weighted Geometric Set Cover} for unit disks and unit squares. We present {quasi-polynomial time approximation schemes} (QPTASs) for both of the above problems in planar graphs: given an accuracy parameter epsilon>0 we can compute a solution whose weight is within multiplicative factor of (1+epsilon) from the optimum in time 2^{poly(1/epsilon,log |D|)}* n^{O(1)}, where n is the number of vertices of the input graph. Our main technical contribution is to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek, Har-Peled, and Wiese [Adamaszek and Wiese, 2013; Adamaszek and Wiese, 2014; Sariel Har-Peled, 2014] to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.
Cite as

Michal Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{pilipczuk_et_al:LIPIcs.ESA.2018.65,
  author =	{Pilipczuk, Michal and van Leeuwen, Erik Jan and Wiese, Andreas},
  title =	{{Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.65},
  URN =		{urn:nbn:de:0030-drops-95282},
  doi =		{10.4230/LIPIcs.ESA.2018.65},
  annote =	{Keywords: QPTAS, planar graphs, Voronoi diagram}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.3
Vietoris-Rips and Cech Complexes of Metric Gluings

Authors: Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We study Vietoris-Rips and Cech complexes of metric wedge sums and metric gluings. We show that the Vietoris-Rips (resp. Cech) complex of a wedge sum, equipped with a natural metric, is homotopy equivalent to the wedge sum of the Vietoris-Rips (resp. Cech) complexes. We also provide generalizations for certain metric gluings, i.e. when two metric spaces are glued together along a common isometric subset. As our main example, we deduce the homotopy type of the Vietoris-Rips complex of two metric graphs glued together along a sufficiently short path. As a result, we can describe the persistent homology, in all homological dimensions, of the Vietoris-Rips complexes of a wide class of metric graphs.
Cite as

Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier. Vietoris-Rips and Cech Complexes of Metric Gluings. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.SoCG.2018.3,
  author =	{Adamaszek, Michal and Adams, Henry and Gasparovic, Ellen and Gommel, Maria and Purvine, Emilie and Sazdanovic, Radmila and Wang, Bei and Wang, Yusu and Ziegelmeier, Lori},
  title =	{{Vietoris-Rips and Cech Complexes of Metric Gluings}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.3},
  URN =		{urn:nbn:de:0030-drops-87162},
  doi =		{10.4230/LIPIcs.SoCG.2018.3},
  annote =	{Keywords: Vietoris-Rips and Cech complexes, metric space gluings and wedge sums, metric graphs, persistent homology}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.42
Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking

Authors: Michal Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlapping rectangles. The problem is notoriously hard both in the approximation and in the parameterized setting. The best known polynomial-time approximation algorithms achieve super-constant approximation ratios [Chalermsook & Chuzhoy, Proc. SODA 2009; Chan & Har-Peled, Discrete & Comp. Geometry, 2012], even though there is a (1+epsilon)-approximation running in quasi-polynomial time [Adamaszek & Wiese, Proc. FOCS 2013; Chuzhoy & Ene, Proc. FOCS 2016]. When parameterized by the target size of the solution, the problem is W[1]-hard even in the unweighted setting [Marx, ESA 2005]. To achieve tractability, we study the following shrinking model: one is allowed to shrink each input rectangle by a multiplicative factor 1-delta for some fixed delta > 0, but the performance is still compared against the optimal solution for the original, non-shrunk instance. We prove that in this regime, the problem admits an EPTAS with running time f(epsilon,delta) n^{O(1)}, and an FPT algorithm with running time f(k,delta) n^{O(1)}, in the setting where a maximum-weight solution of size at most k is to be computed. This improves and significantly simplifies a PTAS given earlier for this problem [Adamaszek, Chalermsook & Wiese, Proc. APPROX/RANDOM 2015], and provides the first parameterized results for the shrinking model. Furthermore, we explore kernelization in the shrinking model, by giving efficient kernelization procedures for several variants of the problem when the input rectangles are squares.
Cite as

Michal Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese. Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{pilipczuk_et_al:LIPIcs.MFCS.2017.42,
  author =	{Pilipczuk, Michal and van Leeuwen, Erik Jan and Wiese, Andreas},
  title =	{{Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.42},
  URN =		{urn:nbn:de:0030-drops-80917},
  doi =		{10.4230/LIPIcs.MFCS.2017.42},
  annote =	{Keywords: Combinatorial optimization, Approximation algorithms, Fixed-parameter algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2442
Large-Girth Roots of Graphs

Authors: Anna Adamaszek and Michal Adamaszek

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for $r$-th powers of graphs of girth at least $2r+3$, thus improving a bound conjectured by Farzad et al. (STACS 2009). Our algorithm also finds all $r$-th roots of a given graph that have girth at least $2r+3$ and no degree one vertices, which is a step towards a recent conjecture of Levenshtein that such root should be unique. On the negative side, we prove that recognition becomes an NP-complete problem when the bound on girth is about twice smaller. Similar results have so far only been attempted for $r=2,3$.
Cite as

Anna Adamaszek and Michal Adamaszek. Large-Girth Roots of Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 35-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.STACS.2010.2442,
  author =	{Adamaszek, Anna and Adamaszek, Michal},
  title =	{{Large-Girth Roots of Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{35--46},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2442},
  URN =		{urn:nbn:de:0030-drops-24429},
  doi =		{10.4230/LIPIcs.STACS.2010.2442},
  annote =	{Keywords: Graph roots, Graph powers, NP-completeness, Recognition algorithms}
}
  • Refine by Author
  • 2 Adamaszek, Michal
  • 2 Pilipczuk, Michal
  • 2 Wiese, Andreas
  • 2 van Leeuwen, Erik Jan
  • 1 Adamaszek, Anna
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Packing and covering problems

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 Combinatorial optimization
  • 1 Fixed-parameter algorithms
  • 1 Graph powers
  • 1 Graph roots
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2018
  • 1 2010
  • 1 2017

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