Search Results

Documents authored by Antoniadis, Antonios

Document
DOI: 10.4230/LIPIcs.ESA.2022.9
Computing Smallest Convex Intersecting Polygons

Authors: Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
A polygon C is an intersecting polygon for a set O of objects in ℝ² if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n. Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments.
Cite as

Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos. Computing Smallest Convex Intersecting Polygons. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.ESA.2022.9,
  author =	{Antoniadis, Antonios and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Skarlatos, Antonis},
  title =	{{Computing Smallest Convex Intersecting Polygons}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.9},
  URN =		{urn:nbn:de:0030-drops-169470},
  doi =		{10.4230/LIPIcs.ESA.2022.9},
  annote =	{Keywords: convex hull, imprecise points, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.9
A Novel Prediction Setup for Online Speed-Scaling

Authors: Antonios Antoniadis, Peyman Jabbarzade, and Golnoosh Shahkarami

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Given the rapid rise in energy demand by data centers and computing systems in general, it is fundamental to incorporate energy considerations when designing (scheduling) algorithms. Machine learning can be a useful approach in practice by predicting the future load of the system based on, for example, historical data. However, the effectiveness of such an approach highly depends on the quality of the predictions and can be quite far from optimal when predictions are sub-par. On the other hand, while providing a worst-case guarantee, classical online algorithms can be pessimistic for large classes of inputs arising in practice. This paper, in the spirit of the new area of machine learning augmented algorithms, attempts to obtain the best of both worlds for the classical, deadline based, online speed-scaling problem: Based on the introduction of a novel prediction setup, we develop algorithms that (i) obtain provably low energy-consumption in the presence of adequate predictions, and (ii) are robust against inadequate predictions, and (iii) are smooth, i.e., their performance gradually degrades as the prediction error increases.
Cite as

Antonios Antoniadis, Peyman Jabbarzade, and Golnoosh Shahkarami. A Novel Prediction Setup for Online Speed-Scaling. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.SWAT.2022.9,
  author =	{Antoniadis, Antonios and Jabbarzade, Peyman and Shahkarami, Golnoosh},
  title =	{{A Novel Prediction Setup for Online Speed-Scaling}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.9},
  URN =		{urn:nbn:de:0030-drops-161693},
  doi =		{10.4230/LIPIcs.SWAT.2022.9},
  annote =	{Keywords: learning augmented algorithms, speed-scaling, energy-efficiency, scheduling theory, online algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.10
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods

Authors: Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, and Daniel Vaz

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in ℝ^d, with d ≥ 3, are NP-hardness and an O(log³ n)-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in ℝ^d is APX-hard for any d ≥ 3. More generally, this implies that TSP with k-dimensional flats does not admit a PTAS for any 1 ≤ k ≤ d-2 unless P = NP, which gives a complete classification regarding the existence of polynomial time approximation schemes for these problems, as there are known PTASes for k = 0 (i.e., points) and k = d-1 (hyperplanes). We are able to give a stronger inapproximability factor for d = O(log n) by showing that TSP with lines does not admit a (2-ε)-approximation in d dimensions under the Unique Games Conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an O(log² n)-approximation algorithm for the problem, albeit with a running time of n^{O(log log n)}.
Cite as

Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, and Daniel Vaz. On the Approximability of the Traveling Salesman Problem with Line Neighborhoods. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.SWAT.2022.10,
  author =	{Antoniadis, Antonios and Kisfaludi-Bak, S\'{a}ndor and Laekhanukit, Bundit and Vaz, Daniel},
  title =	{{On the Approximability of the Traveling Salesman Problem with Line Neighborhoods}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.10},
  URN =		{urn:nbn:de:0030-drops-161706},
  doi =		{10.4230/LIPIcs.SWAT.2022.10},
  annote =	{Keywords: Traveling Salesman with neighborhoods, Group Steiner Tree, Geometric approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.51
Skeletons and Minimum Energy Scheduling

Authors: Antonios Antoniadis, Gunjan Kumar, and Nikhil Kumar

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Consider the problem where n jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor has two available states: a sleep state where no energy is consumed but also no processing can take place, and an active state which consumes energy at a rate of one, and in which jobs can be processed. Transitioning from the active to the sleep does not incur any further energy cost, but transitioning from the sleep to the active state requires q energy units. Jobs may be preempted and (in the multi-processor case) migrated. The single-processor case of the problem is known to be solvable in polynomial time via an involved dynamic program, whereas the only known approximation algorithm for the multi-processor case attains an approximation factor of 3 and is based on rounding the solution to a linear programming relaxation of the problem. In this work, we present efficient and combinatorial approximation algorithms for both the single- and the multi-processor setting. Before, only an algorithm based on linear programming was known for the multi-processor case. Our algorithms build upon the concept of a skeleton, a basic (and not necessarily feasible) schedule that captures the fact that some processor(s) must be active at some time point during an interval. Finally, we further demonstrate the power of skeletons by providing a 2-approximation algorithm for the multiprocessor case, thus improving upon the recent breakthrough 3-approximation result. Our algorithm is based on a novel rounding scheme of a linear-programming relaxation of the problem which incorporates skeletons.
Cite as

Antonios Antoniadis, Gunjan Kumar, and Nikhil Kumar. Skeletons and Minimum Energy Scheduling. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.ISAAC.2021.51,
  author =	{Antoniadis, Antonios and Kumar, Gunjan and Kumar, Nikhil},
  title =	{{Skeletons and Minimum Energy Scheduling}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{51:1--51:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.51},
  URN =		{urn:nbn:de:0030-drops-154849},
  doi =		{10.4230/LIPIcs.ISAAC.2021.51},
  annote =	{Keywords: scheduling, energy-efficiency, approximation algorithms, dynamic programming, combinatorial algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.17
Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop

Authors: Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis, and Pavel Veselý

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output ports, and a buffer with a specific capacity. In each time step, an arbitrary number of packets arrive at the input port, each packet designated for one output port. Each packet is added to the queue of the respective output port. If the total number of packets exceeds the capacity of the buffer, some packets have to be irrevocably rejected. At the end of each time step, each output port transmits a packet in its queue and the goal is to maximize the number of transmitted packets. The Longest Queue Drop (LQD) online algorithm accepts any arriving packet to the buffer. However, if this results in the buffer exceeding its memory capacity, then LQD drops a packet from the back of whichever queue is currently the longest, breaking ties arbitrarily. The LQD algorithm was first introduced in 1991, and is known to be 2-competitive since 2001. Although LQD remains the best known online algorithm for the problem and is of practical interest, determining its true competitiveness is a long-standing open problem. We show that LQD is 1.707-competitive, establishing the first (2-ε) upper bound for the competitive ratio of LQD, for a constant ε > 0.
Cite as

Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis, and Pavel Veselý. Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.ICALP.2021.17,
  author =	{Antoniadis, Antonios and Englert, Matthias and Matsakis, Nicolaos and Vesel\'{y}, Pavel},
  title =	{{Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.17},
  URN =		{urn:nbn:de:0030-drops-140864},
  doi =		{10.4230/LIPIcs.ICALP.2021.17},
  annote =	{Keywords: buffer management, online scheduling, online algorithms, longest queue drop}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.8
On the Complexity of Anchored Rectangle Packing

Authors: Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In the Anchored Rectangle Packing (ARP) problem, we are given a set of points P in the unit square [0,1]^2 and seek a maximum-area set of axis-aligned interior-disjoint rectangles S, each of which is anchored at a point p in P. In the most prominent variant - Lower-Left-Anchored Rectangle Packing (LLARP) - rectangles are anchored in their lower-left corner. Freedman [W. T. Tutte (Ed.), 1969] conjectured in 1969 that, if (0,0) in P, then there is a LLARP that covers an area of at least 0.5. Somewhat surprisingly, this conjecture remains open to this day, with the best known result covering an area of 0.091 [Dumitrescu and Tóth, 2015]. Maybe even more surprisingly, it is not known whether LLARP - or any ARP-problem with only one anchor - is NP-hard. In this work, we first study the Center-Anchored Rectangle Packing (CARP) problem, where rectangles are anchored in their center. We prove NP-hardness and provide a PTAS. In fact, our PTAS applies to any ARP problem where the anchor lies in the interior of the rectangles. Afterwards, we turn to the LLARP problem and investigate two different resource-augmentation settings: In the first we allow an epsilon-perturbation of the input P, whereas in the second we permit an epsilon-overlap between rectangles. For the former setting, we give an algorithm that covers at least as much area as an optimal solution of the original problem. For the latter, we give an (1 - epsilon)-approximation.
Cite as

Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke. On the Complexity of Anchored Rectangle Packing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.ESA.2019.8,
  author =	{Antoniadis, Antonios and Biermeier, Felix and Cristi, Andr\'{e}s and Damerius, Christoph and Hoeksma, Ruben and Kaaser, Dominik and Kling, Peter and N\"{o}lke, Lukas},
  title =	{{On the Complexity of Anchored Rectangle Packing}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.8},
  URN =		{urn:nbn:de:0030-drops-111297},
  doi =		{10.4230/LIPIcs.ESA.2019.8},
  annote =	{Keywords: anchored rectangle, rectangle packing, resource augmentation, PTAS, NP, hardness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.5
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
DOI: 10.4230/LIPIcs.ICALP.2017.31
A QPTAS for the General Scheduling Problem with Identical Release Dates

Authors: Antonios Antoniadis, Ruben Hoeksma, Julie Meißner, José Verschae, and Andreas Wiese

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
The General Scheduling Problem (GSP) generalizes scheduling problems with sum of cost objectives such as weighted flow time and weighted tardiness. Given a set of jobs with processing times, release dates, and job dependent cost functions, we seek to find a minimum cost preemptive schedule on a single machine. The best known algorithm for this problem and also for weighted flow time/tardiness is an O(loglog P)-approximation (where P denotes the range of the job processing times), while the best lower bound shows only strong NP-hardness. When release dates are identical there is also a gap: the problem remains strongly NP-hard and the best known approximation algorithm has a ratio of e+\epsilon (running in quasi-polynomial time). We reduce the latter gap by giving a QPTAS if the numbers in the input are quasi-polynomially bounded, ruling out the existence of an APX-hardness proof unless NP\subseteq DTIME(2^polylog(n)). Our techniques are based on the QPTAS known for the UFP-Cover problem, a particular case of GSP where we must pick a subset of intervals (jobs) on the real line with associated heights and costs. If an interval is selected, its height will help cover a given demand on any point contained within the interval. We reduce our problem to a generalization of UFP-Cover and use a sophisticated divide-and-conquer procedure with interdependent non-symmetric subproblems. We also present a pseudo-polynomial time approximation scheme for two variants of UFP-Cover. For the case of agreeable intervals we give an algorithm based on a new dynamic programming approach which might be useful for other problems of this type. The second one is a resource augmentation setting where we are allowed to slightly enlarge each interval.
Cite as

Antonios Antoniadis, Ruben Hoeksma, Julie Meißner, José Verschae, and Andreas Wiese. A QPTAS for the General Scheduling Problem with Identical Release Dates. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.ICALP.2017.31,
  author =	{Antoniadis, Antonios and Hoeksma, Ruben and Mei{\ss}ner, Julie and Verschae, Jos\'{e} and Wiese, Andreas},
  title =	{{A QPTAS for the General Scheduling Problem with Identical Release Dates}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.31},
  URN =		{urn:nbn:de:0030-drops-74575},
  doi =		{10.4230/LIPIcs.ICALP.2017.31},
  annote =	{Keywords: Generalized Scheduling, QPTAS, Unsplittable Flows}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.6
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
DOI: 10.4230/LIPIcs.STACS.2014.63
Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules

Authors: Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem.
Cite as

Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 63-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.STACS.2014.63,
  author =	{Antoniadis, Antonios and Barcelo, Neal and Consuegra, Mario and Kling, Peter and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele},
  title =	{{Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{63--74},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.63},
  URN =		{urn:nbn:de:0030-drops-44474},
  doi =		{10.4230/LIPIcs.STACS.2014.63},
  annote =	{Keywords: scheduling, flow time, energy efficiency, speed scaling, primal-dual}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.531
Balanced Interval Coloring

Authors: Antonios Antoniadis, Falk Hueffner, Pascal Lenzner, Carsten Moldenhauer, and Alexander Souza

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We consider the discrepancy problem of coloring n intervals with k colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is minimal. Somewhat surprisingly, a coloring with maximal difference at most one always exists. Furthermore, we give an algorithm with running time O(n log n + kn log k) for its construction. This is in particular interesting because many known results for discrepancy problems are non-constructive. This problem naturally models a load balancing scenario, where $n$~tasks with given start- and endtimes have to be distributed among $k$~servers. Our results imply that this can be done ideally balanced. When generalizing to $d$-dimensional boxes (instead of intervals), a solution with difference at most one is not always possible. We show that for any d >= 2 and any k >= 2 it is NP-complete to decide if such a solution exists, which implies also NP-hardness of the respective minimization problem. In an online scenario, where intervals arrive over time and the color has to be decided upon arrival, the maximal difference in the size of color classes can become arbitrarily high for any online algorithm.
Cite as

Antonios Antoniadis, Falk Hueffner, Pascal Lenzner, Carsten Moldenhauer, and Alexander Souza. Balanced Interval Coloring. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 531-542, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.STACS.2011.531,
  author =	{Antoniadis, Antonios and Hueffner, Falk and Lenzner, Pascal and Moldenhauer, Carsten and Souza, Alexander},
  title =	{{Balanced Interval Coloring}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{531--542},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.531},
  URN =		{urn:nbn:de:0030-drops-30413},
  doi =		{10.4230/LIPIcs.STACS.2011.531},
  annote =	{Keywords: Load balancing, discrepancy theory, NP-hardness}
}
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