3 Search Results for "Paluch, Katarzyna"

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-dev.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-dev.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-dev.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}
}
  • Refine by Author
  • 3 Paluch, Katarzyna
  • 1 Adamaszek, Anna
  • 1 Elbassioni, Khaled
  • 1 Mnich, Matthias
  • 1 Wasylkiewicz, Mateusz
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 approximation algorithm
  • 1 cycle cover
  • 1 maximum asymmetric traveling salesman problem
  • 1 restricted 2-matchings
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2012
  • 1 2018
  • 1 2021

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