11 Search Results for "Adamaszek, Anna"


Document
Track A: Algorithms, Complexity and Games
Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects

Authors: Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal, and Andreas Wiese

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We study the geometric knapsack problem in which we are given a set of d-dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that can be packed non-overlappingly into a given d-dimensional (unit hypercube) knapsack. Even if d = 2 and all input objects are disks, this problem is known to be NP-hard [Demaine, Fekete, Lang, 2010]. In this paper, we give polynomial time (1+ε)-approximation algorithms for the following types of input objects in any constant dimension d: - disks and hyperspheres, - a class of fat convex polygons that generalizes regular k-gons for k ≥ 5 (formally, polygons with a constant number of edges, whose lengths are in a bounded range, and in which each angle is strictly larger than π/2), - arbitrary fat convex objects that are sufficiently small compared to the knapsack. We remark that in our PTAS for disks and hyperspheres, we output the computed set of objects, but for a O_ε(1) of them we determine their coordinates only up to an exponentially small error. However, it is not clear whether there always exists a (1+ε)-approximate solution that uses only rational coordinates for the disks' centers. We leave this as an open problem which is related to well-studied geometric questions in the realm of circle packing.

Cite as

Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal, and Andreas Wiese. Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{acharya_et_al:LIPIcs.ICALP.2024.8,
  author =	{Acharya, Pritam and Bhore, Sujoy and Gupta, Aaryan and Khan, Arindam and Mondal, Bratin and Wiese, Andreas},
  title =	{{Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.8},
  URN =		{urn:nbn:de:0030-drops-201511},
  doi =		{10.4230/LIPIcs.ICALP.2024.8},
  annote =	{Keywords: Approximation Algorithms, Polygon Packing, Circle Packing, Sphere Packing, Geometric Knapsack, Resource Augmentation}
}
Document
Track A: Algorithms, Complexity and Games
Sublinear Algorithms for TSP via Path Covers

Authors: Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, and Amin Saberi

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related maximum path cover problem, which asks for a collection of vertex disjoint paths that include the maximum number of edges. We show that for any fixed ε > 0, there is an algorithm that (1/2 - ε)-approximates the maximum path cover size of an n-vertex graph in Õ(n) time. This improves upon a (3/8-ε)-approximate Õ(n √n)-time algorithm of Chen, Kannan, and Khanna [ICALP'20]. Equipped with our path cover algorithm, we give an Õ(n) time algorithm that estimates the cost of (1,2)-TSP within a factor of (1.5+ε) which is an improvement over a folklore (1.75 + ε)-approximate Õ(n)-time algorithm, as well as a (1.625+ε)-approximate Õ(n√n)-time algorithm of [CHK ICALP'20]. For graphic TSP, we present an Õ(n) algorithm that estimates the cost of graphic TSP within a factor of 1.83 which is an improvement over a 1.92-approximate Õ(n) time algorithm due to [CHK ICALP'20, Behnezhad FOCS'21]. We show that the approximation can be further improved to 1.66 using n^{2-Ω(1)} time. All of our Õ(n) time algorithms are information-theoretically time-optimal up to polylog n factors. Additionally, we show that our approximation guarantees for path cover and (1,2)-TSP hit a natural barrier: We show better approximations require better sublinear time algorithms for the well-studied maximum matching problem.

Cite as

Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, and Amin Saberi. Sublinear Algorithms for TSP via Path Covers. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{behnezhad_et_al:LIPIcs.ICALP.2024.19,
  author =	{Behnezhad, Soheil and Roghani, Mohammad and Rubinstein, Aviad and Saberi, Amin},
  title =	{{Sublinear Algorithms for TSP via Path Covers}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.19},
  URN =		{urn:nbn:de:0030-drops-201623},
  doi =		{10.4230/LIPIcs.ICALP.2024.19},
  annote =	{Keywords: Sublinear Algorithms, Traveling Salesman Problem, Approximation Algorithm, (1, 2)-TSP, Graphic TSP}
}
Document
Track A: Algorithms, Complexity and Games
Non-Linear Paging

Authors: Ilan Doron-Arad and Joseph (Seffi) Naor

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We formulate and study non-linear paging - a broad model of online paging where the size of subsets of pages is determined by a monotone non-linear set function of the pages. This model captures the well-studied classic weighted paging and generalized paging problems, and also submodular and supermodular paging, studied here for the first time, that have a range of applications from virtual memory to machine learning. Unlike classic paging, the cache threshold parameter k does not yield good competitive ratios for non-linear paging. Instead, we introduce a novel parameter 𝓁 that generalizes the notion of cache size to the non-linear setting. We obtain a tight deterministic 𝓁-competitive algorithm for general non-linear paging and a o(log²𝓁)-competitive lower bound for randomized algorithms. Our algorithm is based on a new generic LP for the problem that captures both submodular and supermodular paging, in contrast to LPs used for submodular cover settings. We finally focus on the supermodular paging problem, which is a variant of online set cover and online submodular cover, where sets are repeatedly requested to be removed from the cover. We obtain polylogarithmic lower and upper bounds and an offline approximation algorithm.

Cite as

Ilan Doron-Arad and Joseph (Seffi) Naor. Non-Linear Paging. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.57,
  author =	{Doron-Arad, Ilan and Naor, Joseph (Seffi)},
  title =	{{Non-Linear Paging}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{57:1--57:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.57},
  URN =		{urn:nbn:de:0030-drops-202000},
  doi =		{10.4230/LIPIcs.ICALP.2024.57},
  annote =	{Keywords: paging, competitive analysis, non-linear paging, submodular and supermodular functions}
}
Document
Track A: Algorithms, Complexity and Games
Caching Connections in Matchings

Authors: Yaniv Sadeh and Haim Kaplan

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
Motivated by the desire to utilize a limited number of configurable optical switches by recent advances in Software Defined Networks (SDNs), we define an online problem which we call the Caching in Matchings problem. This problem has a natural combinatorial structure and therefore may find additional applications in theory and practice. In the Caching in Matchings problem our cache consists of k matchings of connections between servers that form a bipartite graph. To cache a connection we insert it into one of the k matchings possibly evicting at most two other connections from this matching. This problem resembles the problem known as Connection Caching [Cohen et al., 2000], where we also cache connections but our only restriction is that they form a graph with bounded degree k. Our results show a somewhat surprising qualitative separation between the problems: The competitive ratio of any online algorithm for caching in matchings must depend on the size of the graph. Specifically, we give a deterministic O(nk) competitive and randomized O(n log k) competitive algorithms for caching in matchings, where n is the number of servers and k is the number of matchings. We also show that the competitive ratio of any deterministic algorithm is Ω(max(n/k,k)) and of any randomized algorithm is Ω(log (n/(k² log k)) ⋅ log k). In particular, the lower bound for randomized algorithms is Ω(log n) regardless of k, and can be as high as Ω(log² n) if k = n^{1/3}, for example. We also show that if we allow the algorithm to use at least 2k-1 matchings compared to k used by the optimum then we match the competitive ratios of connection catching which are independent of n. Interestingly, we also show that even a single extra matching for the algorithm allows to get substantially better bounds.

Cite as

Yaniv Sadeh and Haim Kaplan. Caching Connections in Matchings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 120:1-120:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{sadeh_et_al:LIPIcs.ICALP.2024.120,
  author =	{Sadeh, Yaniv and Kaplan, Haim},
  title =	{{Caching Connections in Matchings}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{120:1--120:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.120},
  URN =		{urn:nbn:de:0030-drops-202639},
  doi =		{10.4230/LIPIcs.ICALP.2024.120},
  annote =	{Keywords: Caching, Matchings, Caching in Matchings, Edge Coloring, Online Algorithms}
}
Document
Approximation Algorithms for the Airport and Railway Problem

Authors: Mohammad R. Salavatipour and Lijiangnan Tian

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)


Abstract
In this paper, we present approximation algorithms for the airport and railway problem (AR) on several classes of graphs. The AR problem, introduced by [Anna Adamaszek et al., 2016], is a combination of the Capacitated Facility Location problem (CFL) and the network design problem. An AR instance consists of a set of points (cities) V in a metric d(.,.), each of which is associated with a non-negative cost f_v and a number k, which represent respectively the cost of establishing an airport (facility) in the corresponding point, and the universal airport capacity. A feasible solution is a network of airports and railways providing services to all cities without violating any capacity, where railways are edges connecting pairs of points, with their costs equivalent to the distance between the respective points. The objective is to find such a network with the least cost. In other words, find a forest, each component having at most k points and one open facility, minimizing the total cost of edges and airport opening costs. Adamaszek et al. [Anna Adamaszek et al., 2016] presented a PTAS for AR in the two-dimensional Euclidean metric ℝ² with a uniform opening cost. In subsequent work [Anna Adamaszek et al., 2018] presented a bicriteria 4/3 (2+1/α)-approximation algorithm for AR with non-uniform opening costs but violating the airport capacity by a factor of 1+α, i.e. (1+α)k capacity where 0 < α ≤ 1, a (2+k/(k-1)+ε)-approximation algorithm and a bicriteria Quasi-Polynomial Time Approximation Scheme (QPTAS) for the same problem in the Euclidean plane ℝ². In this work, we give a 2-approximation for AR with a uniform opening cost for general metrics and an O(log n)-approximation for non-uniform opening costs. We also give a QPTAS for AR with a uniform opening cost in graphs of bounded treewidth and a QPTAS for a slightly relaxed version in the non-uniform setting. The latter implies O(1)-approximation on graphs of bounded doubling dimensions, graphs of bounded highway dimensions and planar graphs in quasi-polynomial time.

Cite as

Mohammad R. Salavatipour and Lijiangnan Tian. Approximation Algorithms for the Airport and Railway Problem. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{salavatipour_et_al:LIPIcs.SWAT.2024.40,
  author =	{Salavatipour, Mohammad R. and Tian, Lijiangnan},
  title =	{{Approximation Algorithms for the Airport and Railway Problem}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.40},
  URN =		{urn:nbn:de:0030-drops-200806},
  doi =		{10.4230/LIPIcs.SWAT.2024.40},
  annote =	{Keywords: Facility Location, Approximation Algorithms, Dynamic Programming}
}
Document
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
Approximating Airports and Railways

Authors: Anna Adamaszek, Antonios Antoniadis, Amit Kumar, and Tobias Mömke

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)


Abstract
In this paper we consider the airport and railway problem (AR), which combines capacitated facility location with network design, both in the general metric and the two-dimensional Euclidean space. An instance of the airport and railway problem consists of a set of points in the corresponding metric, together with a non-negative weight for each point, and a parameter k. The points represent cities, the weights denote costs of opening an airport in the corresponding city, and the parameter k is a maximum capacity of an airport. The goal is to construct a minimum cost network of airports and railways connecting all the cities, where railways correspond to edges connecting pairs of points, and the cost of a railway is equal to the distance between the corresponding points. The network is partitioned into components, where each component contains an open airport, and spans at most k cities. For the Euclidean case, any points in the plane can be used as Steiner vertices of the network. We obtain the first bicriteria approximation algorithm for AR for the general metric case, which yields a 4-approximate solution with a resource augmentation of the airport capacity k by a factor of 2. More generally, for any parameter 0 < p <= 1 where pk is an integer we develop a (4/3)(2 + 1/p)-approximation algorithm for metric AR with a resource augmentation by a factor of 1 + p. Furthermore, we obtain the first constant factor approximation algorithm that does not resort to resource augmentation for AR in the Euclidean plane. Additionally, for the Euclidean setting we provide a quasi-polynomial time approximation scheme for the same problem with a resource augmentation by a factor of 1 + mu on the airport capacity, for any fixed mu > 0.

Cite as

Anna Adamaszek, Antonios Antoniadis, Amit Kumar, and Tobias Mömke. Approximating Airports and Railways. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.STACS.2018.5,
  author =	{Adamaszek, Anna and Antoniadis, Antonios and Kumar, Amit and M\"{o}mke, Tobias},
  title =	{{Approximating Airports and Railways}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.5},
  URN =		{urn:nbn:de:0030-drops-85183},
  doi =		{10.4230/LIPIcs.STACS.2018.5},
  annote =	{Keywords: Network Design, Facility Location, Approximation Algorithms, PTAS, Metric, Euclidean}
}
Document
Irrational Guards are Sometimes Needed

Authors: Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


Abstract
In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon so that the guards together can see the whole polygon. We say that a guard at position x sees a point y if the line segment xy is contained in the polygon. Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. Otherwise, four guards are needed. By extending this example, we show that for every n, there is a polygon which can be guarded by 3n guards with irrational coordinates but needs 4n guards if the coordinates have to be rational. Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.

Cite as

Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational Guards are Sometimes Needed. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.3,
  author =	{Abrahamsen, Mikkel and Adamaszek, Anna and Miltzow, Tillmann},
  title =	{{Irrational Guards are Sometimes Needed}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.3},
  URN =		{urn:nbn:de:0030-drops-71946},
  doi =		{10.4230/LIPIcs.SoCG.2017.3},
  annote =	{Keywords: art gallery problem, computational geometry, irrational numbers}
}
Document
Airports and Railways: Facility Location Meets Network Design

Authors: Anna Adamaszek, Antonios Antoniadis, and Tobias Mömke

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)


Abstract
We introduce a new framework of Airport and Railway Problems, which combines capacitated facility location with network design. In this framework we are given a graph with weights on the vertices and on the edges, together with a parameter k. The vertices of the graph represent cities, and weights denote respectively the costs of opening airports in the cities and building railways that connect pairs of cities. The parameter $k$ can be thought of as the capacity of an airport. The goal is to construct a minimum cost network of airports and railways connecting the cities, where each connected component in the network spans at most k vertices, contains an open airport, and the network satisfies some additional requirements specific to the problem in the framework. We consider two problems in this framework. In the AR_F problem there are no additional requirements for the network. This problem is related to capacitated facility location. In the AR_P problem, we require each component to be a path with airports at both endpoints. AR_P is a relaxation of the capacitated vehicle routing problem (CVRP). We consider the problems in the two-dimensional Euclidean setting. We show that both AR_F and AR_P are NP-hard, even for uniform vertex weights (i.e., when the cost of building an airport is the same for all cities). On the positive side, we provide polynomial time approximation schemes for AR_F and AR_P when vertex weights are uniform. We also investigate AR_F and AR_P for k = infinity. In this setting we present an exact polynomial time algorithm for AR_F with general vertex costs, which also works for general edge costs. In contrast to AR_F, AR_P remains NP-hard when k = infinity, and we present a polynomial time approximation scheme for general vertex weights. We believe that our PTAS for AR_P with uniform vertex weights and arbitrary k brings us closer towards a PTAS for Euclidean CVRP, for which the main difficulty is to deal with paths of length at most k.

Cite as

Anna Adamaszek, Antonios Antoniadis, and Tobias Mömke. Airports and Railways: Facility Location Meets Network Design. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.STACS.2016.6,
  author =	{Adamaszek, Anna and Antoniadis, Antonios and M\"{o}mke, Tobias},
  title =	{{Airports and Railways: Facility Location Meets Network Design}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.6},
  URN =		{urn:nbn:de:0030-drops-57074},
  doi =		{10.4230/LIPIcs.STACS.2016.6},
  annote =	{Keywords: approximation algorithms, geometric approximation, facility location, network design, PTAS}
}
Document
How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking

Authors: Anna Adamaszek, Parinya Chalermsook, and Andreas Wiese

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


Abstract
In the Maximum Weight Independent Set of Rectangles (MWISR) problem, we are given a collection of weighted axis-parallel rectangles in the plane. Our goal is to compute a maximum weight subset of pairwise non-overlapping rectangles. Due to its various applications, as well as connections to many other problems in computer science, MWISR has received a lot of attention from the computational geometry and the approximation algorithms community. However, despite being extensively studied, MWISR remains not very well understood in terms of polynomial time approximation algorithms, as there is a large gap between the upper and lower bounds, i.e., O(log n\ loglog n) v.s. NP-hardness. Another important, poorly understood question is whether one can color rectangles with at most O(omega(R)) colors where omega(R) is the size of a maximum clique in the intersection graph of a set of input rectangles R. Asplund and Grünbaum obtained an upper bound of O(omega(R)^2) about 50 years ago, and the result has remained asymptotically best. This question is strongly related to the integrality gap of the canonical LP for MWISR. In this paper, we settle above three open problems in a relaxed model where we are allowed to shrink the rectangles by a tiny bit (rescaling them by a factor of 1-delta for an arbitrarily small constant delta > 0. Namely, in this model, we show (i) a PTAS for MWISR and (ii) a coloring with O(omega(R)) colors which implies a constant upper bound on the integrality gap of the canonical LP. For some applications of MWISR the possibility to shrink the rectangles has a natural, well-motivated meaning. Our results can be seen as an evidence that the shrinking model is a promising way to relax a geometric problem for the purpose of better algorithmic results.

Cite as

Anna Adamaszek, Parinya Chalermsook, and Andreas Wiese. How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 43-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.APPROX-RANDOM.2015.43,
  author =	{Adamaszek, Anna and Chalermsook, Parinya and Wiese, Andreas},
  title =	{{How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{43--60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.43},
  URN =		{urn:nbn:de:0030-drops-52936},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.43},
  annote =	{Keywords: Approximation algorithms, independent set, resource augmentation, rectangle intersection graphs, PTAS}
}
Document
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.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
  • 6 Adamaszek, Anna
  • 2 Antoniadis, Antonios
  • 2 Mömke, Tobias
  • 2 Wiese, Andreas
  • 1 Abrahamsen, Mikkel
  • Show More...

  • Refine by Classification
  • 2 Theory of computation
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Graph coloring
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Caching and paging algorithms
  • Show More...

  • Refine by Keyword
  • 3 Approximation Algorithms
  • 3 PTAS
  • 2 Approximation algorithms
  • 2 Facility Location
  • 1 (1
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 5 2024
  • 2 2018
  • 1 2010
  • 1 2015
  • 1 2016
  • Show More...