8 Search Results for "Paluch, Katarzyna"

Document
DOI: 10.4230/LIPIcs.STACS.2026.12
Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density

Authors: Matthias Bentert, Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, and André Nichterlein

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study τ-Bounded-Density Edge Deletion (τ-BDED), where given an undirected graph G, the task is to remove as few edges as possible to obtain a graph G' where no subgraph of G' has density more than τ. The density of a (sub)graph is the number of edges divided by the number of vertices. This problem was recently introduced and shown to be NP-hard for τ ∈ {2/3, 3/4, 1 + 1/25}, but polynomial-time solvable for τ ∈ {0,1/2,1} [Bazgan et al., JCSS 2025]. We provide a complete dichotomy with respect to the target density τ: 1) If 2τ ∈ ℕ (half-integral target density) or τ < 2/3, then τ-BDED is polynomial-time solvable. 2) Otherwise, τ-BDED is NP-hard. We complement the NP-hardness with fixed-parameter tractability with respect to the treewidth of G. Moreover, for integral target density τ ∈ ℕ, we show τ-BDED to be solvable in randomized O(m^{1 + o(1)}) time. Our algorithmic results are based on a reduction to a new general flow problem on restricted networks that, depending on τ, can be solved via Maximum s-t-Flow or General Factors. We believe this connection between these variants of flow and matching to be of independent interest.
Cite as

Matthias Bentert, Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, and André Nichterlein. Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.12,
  author =	{Bentert, Matthias and Breitkopf, Tom-Lukas and Froese, Vincent and Herrmann, Anton and Nichterlein, Andr\'{e}},
  title =	{{Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.12},
  URN =		{urn:nbn:de:0030-drops-255012},
  doi =		{10.4230/LIPIcs.STACS.2026.12},
  annote =	{Keywords: Transshipment, Maximum Flow, General Factors, Matching, Graph Modification Problem}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.93
Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity

Authors: Jingyang Zhao and Mingyu Xiao

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider k-CVRP in general metrics and on general graphs, where k is the vehicle capacity. All three versions are APX-hard for any fixed k ≥ 3. Assume that the approximation ratio of metric TSP is 3/2. We present a (5/2 - Θ(√{1/k}))-approximation algorithm for the splittable and unit-demand cases, and a (5/2 + ln 2 - Θ(√{1/k}))-approximation algorithm for the unsplittable case. Our approximation ratio is better than the previous results when k is less than a sufficiently large value, approximately 1.7 x 10⁷. For small values of k, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the approximation ratio from 1.792 to 1.500 for k = 3, and from 1.750 to 1.500 for k = 4. For the unsplittable case, we improve the approximation ratio from 1.792 to 1.500 for k = 3, from 2.051 to 1.750 for k = 4, and from 2.249 to 2.157 for k = 5. The approximation ratio for k = 3 surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP - an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well.
Cite as

Jingyang Zhao and Mingyu Xiao. Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhao_et_al:LIPIcs.MFCS.2025.93,
  author =	{Zhao, Jingyang and Xiao, Mingyu},
  title =	{{Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{93:1--93:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.93},
  URN =		{urn:nbn:de:0030-drops-242008},
  doi =		{10.4230/LIPIcs.MFCS.2025.93},
  annote =	{Keywords: Combinatorial Optimization, Capacitated Vehicle Routing, Approximation Algorithms, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.9
Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model

Authors: Sharareh Alipour, Ermiya Farokhnejad, and Tobias Mömke

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We investigate semi-streaming algorithms for the Traveling Salesman Problem (TSP). Specifically, we focus on a variant known as the (1,2)-TSP, where the distances between any two vertices are either one or two. Our primary emphasis is on the closely related Maximum Path Cover Problem, which aims to find a collection of vertex-disjoint paths that covers the maximum number of edges in a graph. We propose an algorithm that, for any ε > 0, achieves a (2/3-ε)-approximation of the maximum path cover size for an n-vertex graph, using poly(1/ε) passes. This result improves upon the previous 1/2-approximation by Behnezhad et al. [Soheil Behnezhad et al., 2023] in the semi-streaming model. Building on this result, we design a semi-streaming algorithm that constructs a tour for an instance of (1,2)-TSP with an approximation factor of (4/3 + ε), improving upon the previous 3/2-approximation factor algorithm by Behnezhad et al. [Soheil Behnezhad et al., 2023]. Furthermore, we extend our approach to develop an approximation algorithm for the Maximum TSP (Max-TSP), where the goal is to find a Hamiltonian cycle with the maximum possible weight in a given weighted graph G. Our algorithm provides a (7/12 - ε)-approximation for Max-TSP in poly(1/(ε)) passes, improving on the previously known (1/2-ε)-approximation obtained via maximum weight matching in the semi-streaming model.
Cite as

Sharareh Alipour, Ermiya Farokhnejad, and Tobias Mömke. Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alipour_et_al:LIPIcs.STACS.2025.9,
  author =	{Alipour, Sharareh and Farokhnejad, Ermiya and M\"{o}mke, Tobias},
  title =	{{Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.9},
  URN =		{urn:nbn:de:0030-drops-228342},
  doi =		{10.4230/LIPIcs.STACS.2025.9},
  annote =	{Keywords: (1,2)-TSP, Max-TSP, Maximum Path Cover, Semi-Streaming Algorithms, Approximation Algorithms, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.62
Faster Algorithms on Linear Delta-Matroids

Authors: Tomohiro Koana and Magnus Wahlström

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We present new algorithms and constructions for linear delta-matroids. Delta-matroids are generalizations of matroids that also capture structures such as matchable vertex sets in graphs and path-packing problems. As with matroids, an important class of delta-matroids is given by linear delta-matroids, which generalize linear matroids and are represented via a "twist" of a skew-symmetric matrix. We observe an alternative representation, termed a contraction representation over a skew-symmetric matrix. This representation is equivalent to the more standard twist representation up to O(n^ω)-time transformations (where n is the dimension of the delta-matroid and ω < 2.372 the matrix multiplication exponent), but it is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions for linear delta-matroids. In particular, we show that the union and delta-sum of linear delta-matroids are again linear delta-matroids, and that a representation for the resulting delta-matroid can be constructed in randomized time O(n^ω) (or more precisely, in O(n^ω) field operations, over a field of size at least Ω(n⋅(1/ε)), where ε > 0 is an error parameter). Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single O(n^ω)-time matrix rank computation. Using the methods of Harvey, previously applied by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the O(n⁴)-time augmenting path algorithm of Geelen, Iwata and Murota, albeit with randomization. Finally, we consider the maximum-cardinality delta-matroid intersection problem (equivalently, the maximum-cardinality delta-matroid matching problem). Using Storjohann’s algorithms for symbolic determinants, we show that such a solution can be found in O(n^{ω+1}) time. This provides the first (randomized) polynomial-time solution for the problem, thereby solving an open question of Kakimura and Takamatsu.
Cite as

Tomohiro Koana and Magnus Wahlström. Faster Algorithms on Linear Delta-Matroids. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.STACS.2025.62,
  author =	{Koana, Tomohiro and Wahlstr\"{o}m, Magnus},
  title =	{{Faster Algorithms on Linear Delta-Matroids}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.62},
  URN =		{urn:nbn:de:0030-drops-228876},
  doi =		{10.4230/LIPIcs.STACS.2025.62},
  annote =	{Keywords: Delta-matroids, Randomized algorithms}
}
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}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2024
  • 1 2021
  • 1 2018
  • Show More...

  • Refine by Author
  • 4 Paluch, Katarzyna
  • 1 Adamaszek, Anna
  • 1 Alipour, Sharareh
  • 1 Bentert, Matthias
  • 1 Breitkopf, Tom-Lukas
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Matchings and factors
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Mathematics of computing → Network flows
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 2 Graph Algorithms
  • 1 (1,2)-TSP
  • 1 Approximation algorithms
  • 1 Capacitated Vehicle Routing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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