Search Results

Documents authored by Paluch, Katarzyna

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.28
Rectangle Tiling Binary Arrays

Authors: Pratik Ghosal, Syed Mohammad Meesum, and Katarzyna Paluch

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

Abstract
The problem of rectangle tiling binary arrays is defined as follows. Given an n × n array A of zeros and ones and a natural number p, our task is to partition A into at most p rectangular tiles, so that the maximal weight of a tile is minimized. A tile is any rectangular subarray of A. The weight of a tile is the sum of elements that fall within it. We present a linear (O(n²)) time (3/2 + p²/w(A))-approximation algorithm for this problem, where w(A) denotes the weight of the whole array A. This improves on the previously known approximation with the ratio 2 when p²/w(A) < 1/2. The result is best possible in the following sense. The algorithm employs the lower bound of L = ⌈w(A)/p⌉, which is the only known and used bound on the optimum in all algorithms for rectangle tiling. We prove that a better approximation factor for the binary RTile cannot be achieved using L, because there exist arrays, whose every partition contains a tile with weight at least (3/2 + p/w(A))L. We also consider the dual problem of rectangle tiling for binary arrays, where we are given an upper bound on the weight of the tiles, and we have to cover the array A with the minimum number of non-overlapping tiles. Both problems have natural extensions to d-dimensional versions, for which we provide analogous results.
Cite as

Pratik Ghosal, Syed Mohammad Meesum, and Katarzyna Paluch. Rectangle Tiling Binary Arrays. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ghosal_et_al:LIPIcs.APPROX/RANDOM.2024.28,
  author =	{Ghosal, Pratik and Meesum, Syed Mohammad and Paluch, Katarzyna},
  title =	{{Rectangle Tiling Binary Arrays}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{28:1--28: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.28},
  URN =		{urn:nbn:de:0030-drops-210214},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.28},
  annote =	{Keywords: Rectangle Tiling, RTILE, DRTILE}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.73
Restricted t-Matchings via Half-Edges

Authors: Katarzyna Paluch and Mateusz Wasylkiewicz

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
For a bipartite graph G we consider the problem of finding a maximum size/weight square-free 2-matching and its generalization - the problem of finding a maximum size/weight K_{t,t}-free t-matching, where t is an integer greater than two and K_{t,t} denotes a bipartite clique with t vertices on each of the two sides. Since the weighted versions of these problems are NP-hard in general, we assume that the weights are vertex-induced on any subgraph isomorphic to K_{t,t}. We present simple combinatorial algorithms for these problems. Our algorithms are significantly simpler and faster than those previously known. We dispense with the need to shrink squares and, more generally subgraphs isomorphic to K_{t,t}, the operation which occurred in all previous algorithms for such t-matchings and instead use so-called half-edges. A half-edge of edge e is, informally speaking, a half of e containing exactly one of its endpoints. Additionally, we consider another problem concerning restricted matchings. Given a (not necessarily bipartite) graph G = (V,E), a set of k subsets of edges E₁, E₂, …, E_k and k natural numbers r₁, r₂, …, r_k, the Restricted Matching Problem asks to find a maximum size matching of G among such ones that for each 1 ≤ i ≤ k, M contains at most r_i edges of E_i. This problem is NP-hard even when G is bipartite. We show that it is solvable in polynomial time if (i) for each i the graph G contains a clique or a bipartite clique on all endpoints of E_i; in the case of a bipartite clique it is required to contain E_i and (ii) the sets E₁, …, E_k are almost vertex-disjoint - the endpoints of any two different sets have at most one vertex in common.
Cite as

Katarzyna Paluch and Mateusz Wasylkiewicz. Restricted t-Matchings via Half-Edges. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 73:1-73:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{paluch_et_al:LIPIcs.ESA.2021.73,
  author =	{Paluch, Katarzyna and Wasylkiewicz, Mateusz},
  title =	{{Restricted t-Matchings via Half-Edges}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{73:1--73:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.73},
  URN =		{urn:nbn:de:0030-drops-146541},
  doi =		{10.4230/LIPIcs.ESA.2021.73},
  annote =	{Keywords: restricted 2-matchings}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.9
New Approximation Algorithms for (1,2)-TSP

Authors: Anna Adamaszek, Matthias Mnich, and Katarzyna Paluch

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give faster and simpler approximation algorithms for the (1,2)-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either 1 or 2. Our main results are two approximation algorithms for (1,2)-TSP, one with approximation factor 8/7 and run time O(n^3) and the other having an approximation guarantee of 7/6 and run time O(n^{2.5}). The 8/7-approximation matches the best known approximation factor for (1,2)-TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of O(n^9). Thus, ours is the first improvement for the (1,2)-TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "half-edges". The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an 8/7-approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best 8/7-approximation. The 7/6-approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimum-cost triangle-free cycle cover.
Cite as

Anna Adamaszek, Matthias Mnich, and Katarzyna Paluch. New Approximation Algorithms for (1,2)-TSP. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.ICALP.2018.9,
  author =	{Adamaszek, Anna and Mnich, Matthias and Paluch, Katarzyna},
  title =	{{New Approximation Algorithms for (1,2)-TSP}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.9},
  URN =		{urn:nbn:de:0030-drops-90133},
  doi =		{10.4230/LIPIcs.ICALP.2018.9},
  annote =	{Keywords: Approximation algorithms, traveling salesperson problem, cycle cover}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.501
Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem

Authors: Katarzyna Paluch, Khaled Elbassioni, and Anke van Zuylen

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We give a very simple approximation algorithm for the maximum asymmetric traveling salesman problem. The approximation guarantee of our algorithm is 2/3, which matches the best known approximation guarantee by Kaplan, Lewenstein, Shafrir and Sviridenko. Our algorithm is simple to analyze, and contrary to previous approaches, which need an optimal solution to a linear program, our algorithm is combinatorial and only uses maximum weight perfect matching algorithm.
Cite as

Katarzyna Paluch, Khaled Elbassioni, and Anke van Zuylen. Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 501-506, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{paluch_et_al:LIPIcs.STACS.2012.501,
  author =	{Paluch, Katarzyna and Elbassioni, Khaled and van Zuylen, Anke},
  title =	{{Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{501--506},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.501},
  URN =		{urn:nbn:de:0030-drops-34129},
  doi =		{10.4230/LIPIcs.STACS.2012.501},
  annote =	{Keywords: approximation algorithm, maximum asymmetric traveling salesman problem}
}
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