36 Search Results for "Erlebach, Thomas"

Volume

OASIcs, Volume 14

10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)

ATMOS 2010, September 9, 2010, Liverpool, United Kingdom

Editors: Thomas Erlebach and Marco Lübbecke

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.55
Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous

Authors: Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr.

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

Abstract
Temporal graphs are dynamic graphs where the edge set can change in each time step, while the vertex set stays the same. Exploration of temporal graphs whose snapshot in each time step is a connected graph, called connected temporal graphs, has been widely studied. In this paper, we extend the concept of graph automorphisms from static graphs to temporal graphs and show for the first time that symmetries enable faster exploration: We prove that a connected temporal graph with n vertices and orbit number r (i.e., r is the number of automorphism orbits) can be explored in O(r n^{1+ε}) time steps, for any fixed ε > 0. For r = O(n^c) for constant c < 1, this is a significant improvement over the known tight worst-case bound of Θ(n²) time steps for arbitrary connected temporal graphs. We also give two lower bounds for temporal exploration, showing that Ω(n log n) time steps are required for some inputs with r = O(1) and that Ω(rn) time steps are required for some inputs for any r with 1 ≤ r ≤ n. Moreover, we show that the techniques we develop for fast exploration can be used to derive the following result for rendezvous: Two agents with different programs and without communication ability are placed by an adversary at arbitrary vertices and given full information about the connected temporal graph, except that they do not have consistent vertex labels. Then the two agents can meet at a common vertex after O(n^{1+ε}) time steps, for any constant ε > 0. For some connected temporal graphs with the orbit number being a constant, we also present a complementary lower bound of Ω(nlog n) time steps.
Cite as

Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr.. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dogeas_et_al:LIPIcs.ICALP.2024.55,
  author =	{Dogeas, Konstantinos and Erlebach, Thomas and Kammer, Frank and Meintrup, Johannes and Moses Jr., William K.},
  title =	{{Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{55:1--55:18},
  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.55},
  URN =		{urn:nbn:de:0030-drops-201989},
  doi =		{10.4230/LIPIcs.ICALP.2024.55},
  annote =	{Keywords: dynamic graphs, parameterized algorithms, algorithmic graph theory, graph automorphism, orbit number}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.71
Low-Memory Algorithms for Online Edge Coloring

Authors: Prantar Ghosh and Manuel Stoeckl

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

Abstract
For edge coloring, the online and the W-streaming models seem somewhat orthogonal: the former needs edges to be assigned colors immediately after insertion, typically without any space restrictions, while the latter limits memory to be sublinear in the input size but allows an edge’s color to be announced any time after its insertion. We aim for the best of both worlds by designing small-space online algorithms for edge coloring. Our online algorithms significantly improve upon the memory used by prior ones while achieving an O(1)-competitive ratio. We study the problem under both (adversarial) edge arrivals and vertex arrivals. Under vertex arrivals of any n-node graph with maximum vertex-degree Δ, our online O(Δ)-coloring algorithm uses only semi-streaming space (i.e., Õ(n) space, where the Õ(.) notation hides polylog(n) factors). Under edge arrivals, we obtain an online O(Δ)-coloring in Õ(n√Δ) space. We also achieve a smooth color-space tradeoff: for any t = O(Δ), we get an O(Δt(log²Δ))-coloring in Õ(n√{Δ/t}) space, improving upon the state of the art that used Õ(nΔ/t) space for the same number of colors. The improvements stem from extensive use of random permutations that enable us to avoid previously used colors. Most of our algorithms can be derandomized and extended to multigraphs, where edge coloring is known to be considerably harder than for simple graphs.
Cite as

Prantar Ghosh and Manuel Stoeckl. Low-Memory Algorithms for Online Edge Coloring. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.ICALP.2024.71,
  author =	{Ghosh, Prantar and Stoeckl, Manuel},
  title =	{{Low-Memory Algorithms for Online Edge Coloring}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{71:1--71: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.71},
  URN =		{urn:nbn:de:0030-drops-202146},
  doi =		{10.4230/LIPIcs.ICALP.2024.71},
  annote =	{Keywords: Edge coloring, streaming model, online algorithms}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SAND.2024.1
Exploration and Rendezvous in Temporal Graphs (Invited Talk)

Authors: Thomas Erlebach

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
Given a temporal graph 𝒢 and a start vertex v in 𝒢, the temporal exploration problem (TEXP) is the problem of determining a temporal walk that starts at v and visits all vertices of 𝒢, with the objective of minimizing the time when the last unvisited vertex is reached. Studies have investigated the (parameterized) complexity and approximability of TEXP and the worst-case number of time steps required to complete an exploration. While many upper and lower bounds have been obtained for different settings, there are still some large gaps that pose interesting open problems. In this talk, we will give an overview of known results and techniques as well as open problems. Furthermore, we will discuss recent results (from joint work with Konstantinos Dogeas, Frank Kammer, Johannes Meintrup, and William K. Moses Jr) about exploiting symmetries in temporal graphs to get faster exploration. We view the number of automorphism orbits of the temporal graph as a new parameter, termed the orbit number, that may also be useful in other contexts. Finally, we show how a subroutine for quickly exploring a single orbit of the graph can be exploited to solve a certain rendezvous problem with two agents using a near-linear number of time steps in every always-connected temporal graph.
Cite as

Thomas Erlebach. Exploration and Rendezvous in Temporal Graphs (Invited Talk). In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{erlebach:LIPIcs.SAND.2024.1,
  author =	{Erlebach, Thomas},
  title =	{{Exploration and Rendezvous in Temporal Graphs}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.1},
  URN =		{urn:nbn:de:0030-drops-198797},
  doi =		{10.4230/LIPIcs.SAND.2024.1},
  annote =	{Keywords: Dynamic graphs, parameterized algorithms, orbit number}
}
Document
DOI: 10.4230/LIPIcs.SAND.2024.12
Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization

Authors: Thomas Erlebach, Nils Morawietz, and Petra Wolf

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
In the periodic temporal graph realization problem introduced by Klobas et al. [SAND '24] one is given a period Δ and an n× n matrix D of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph with period Δ such that the fastest travel time between any pair of vertices matches the one specified by D. We generalize the problem from simple temporal graphs to temporal graphs where each edge can appear up to 𝓁 times in each period, for some given integer 𝓁. For the resulting problem Multi-Label Periodic TGR, we show that it is fixed-parameter tractable for parameter n and for parameter vc+Δ, where vc is the vertex cover number of the underlying graph. We also show the existence of a polynomial kernel for parameter nu+d_max, where nu is the number of non-universal vertices of the underlying graph and d_max is the largest entry of D. Furthermore, we show that the problem is NP-hard for each 𝓁 ≥ 5, even if the underlying graph is a tree, a case that was known to be solvable in polynomial time if the task is to construct a simple periodic temporal graph, that is, if 𝓁 = 1.
Cite as

Thomas Erlebach, Nils Morawietz, and Petra Wolf. Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.SAND.2024.12,
  author =	{Erlebach, Thomas and Morawietz, Nils and Wolf, Petra},
  title =	{{Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.12},
  URN =		{urn:nbn:de:0030-drops-198909},
  doi =		{10.4230/LIPIcs.SAND.2024.12},
  annote =	{Keywords: Fixed-Parameter Tractability, Almost-Clique, Kernelization, Dynamic Network, Temporal Graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.49
Package Delivery Using Drones with Restricted Movement Areas

Authors: Thomas Erlebach, Kelin Luo, and Frits C.R. Spieksma

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider the objectives of minimizing the delivery time (problem DDT) and of minimizing the total energy consumption (problem DDC). For general graphs, we show a strong inapproximability result and a matching approximation algorithm for DDT as well as NP-hardness and a 2-approximation algorithm for DDC. For the special case of a path, we show that DDT is NP-hard if the drones have different speeds. For trees, we give optimal algorithms under the assumption that all drones have the same speed or the same energy consumption rate. The results for trees extend to arbitrary graphs if the subgraph of each drone is isometric.
Cite as

Thomas Erlebach, Kelin Luo, and Frits C.R. Spieksma. Package Delivery Using Drones with Restricted Movement Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.ISAAC.2022.49,
  author =	{Erlebach, Thomas and Luo, Kelin and Spieksma, Frits C.R.},
  title =	{{Package Delivery Using Drones with Restricted Movement Areas}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.49},
  URN =		{urn:nbn:de:0030-drops-173343},
  doi =		{10.4230/LIPIcs.ISAAC.2022.49},
  annote =	{Keywords: Mobile agents, approximation algorithm, inapproximability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.49
Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty

Authors: Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter

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

Abstract
We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number of queries needed to solve the minimum spanning tree problem, a fundamental combinatorial optimization problem that has been central also to the research area of explorable uncertainty. For all integral γ ≥ 2, we present algorithms that are γ-robust and (1+1/γ)-consistent, meaning that they use at most γOPT queries if the predictions are arbitrarily wrong and at most (1+1/γ)OPT queries if the predictions are correct, where OPT is the optimal number of queries for the given instance. Moreover, we show that this trade-off is best possible. Furthermore, we argue that a suitably defined hop distance is a useful measure for the amount of prediction error and design algorithms with performance guarantees that degrade smoothly with the hop distance. We also show that the predictions are PAC-learnable in our model. Our results demonstrate that untrusted predictions can circumvent the known lower bound of 2, without any degradation of the worst-case ratio. To obtain our results, we provide new structural insights for the minimum spanning tree problem that might be useful in the context of query-based algorithms regardless of predictions. In particular, we generalize the concept of witness sets - the key to lower-bounding the optimum - by proposing novel global witness set structures and completely new ways of adaptively using those.
Cite as

Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.ESA.2022.49,
  author =	{Erlebach, Thomas and de Lima, Murilo Santos and Megow, Nicole and Schl\"{o}ter, Jens},
  title =	{{Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{49:1--49:18},
  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.49},
  URN =		{urn:nbn:de:0030-drops-169872},
  doi =		{10.4230/LIPIcs.ESA.2022.49},
  annote =	{Keywords: explorable uncertainty, queries, untrusted predictions}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.15
Parameterized Temporal Exploration Problems

Authors: Thomas Erlebach and Jakob T. Spooner

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph 𝒢 admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices. Formally, a temporal graph is a sequence 𝒢 = ⟨ G₁,..., G_L⟩ of graphs with V(G_t) = V(G) and E(G_t) ⊆ E(G) for all t ∈ [L] and some underlying graph G, and a temporal walk is a time-respecting sequence of edge-traversals. For the strict variant, in which edges must be traversed in strictly increasing timesteps, we give FPT algorithms for the problem of finding a temporal walk that visits a given set X of vertices, parameterized by |X|, and for the problem of finding a temporal walk that visits at least k distinct vertices in V, parameterized by k. For the non-strict variant, in which an arbitrary number of edges can be traversed in each timestep, we parameterize by the lifetime L of the input graph and provide an FPT algorithm for the temporal exploration problem. We also give additional FPT or W[2]-hardness results for further problem variants.
Cite as

Thomas Erlebach and Jakob T. Spooner. Parameterized Temporal Exploration Problems. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.SAND.2022.15,
  author =	{Erlebach, Thomas and Spooner, Jakob T.},
  title =	{{Parameterized Temporal Exploration Problems}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.15},
  URN =		{urn:nbn:de:0030-drops-159570},
  doi =		{10.4230/LIPIcs.SAND.2022.15},
  annote =	{Keywords: Temporal graphs, fixed-parameter tractability, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.10
Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty

Authors: Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter

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

Abstract
Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time f(α)-competitive algorithm, where f(α) ∈ [1.618+ε,2] depends on the approximation ratio α for an underlying vertex cover problem. We also show that no algorithm using a similar approach can be better than 1.5-competitive. Furthermore, we give polynomial-time 4/3-competitive algorithms for bipartite graphs with arbitrary query costs and for hypergraphs with a single hyperedge and uniform query costs, with matching lower bounds.
Cite as

Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.ESA.2021.10,
  author =	{Bampis, Evripidis and D\"{u}rr, Christoph and Erlebach, Thomas and de Lima, Murilo Santos and Megow, Nicole and Schl\"{o}ter, Jens},
  title =	{{Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{10:1--10:18},
  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.10},
  URN =		{urn:nbn:de:0030-drops-145910},
  doi =		{10.4230/LIPIcs.ESA.2021.10},
  annote =	{Keywords: Explorable uncertainty, queries, stochastic optimization, graph orientation, selection problems}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.27
Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries

Authors: Thomas Erlebach, Michael Hoffmann, and Murilo Santos de Lima

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
The area of computing with uncertainty considers problems where some information about the input elements is uncertain, but can be obtained using queries. For example, instead of the weight of an element, we may be given an interval that is guaranteed to contain the weight, and a query can be performed to reveal the weight. While previous work has considered models where queries are asked either sequentially (adaptive model) or all at once (non-adaptive model), and the goal is to minimize the number of queries that are needed to solve the given problem, we propose and study a new model where k queries can be made in parallel in each round, and the goal is to minimize the number of query rounds. We use competitive analysis and present upper and lower bounds on the number of query rounds required by any algorithm in comparison with the optimal number of query rounds. Given a set of uncertain elements and a family of m subsets of that set, we present an algorithm for determining the value of the minimum of each of the subsets that requires at most (2+ε) ⋅ opt_k+O(1/(ε) ⋅ lg m) rounds for every 0 < ε < 1, where opt_k is the optimal number of rounds, as well as nearly matching lower bounds. For the problem of determining the i-th smallest value and identifying all elements with that value in a set of uncertain elements, we give a 2-round-competitive algorithm. We also show that the problem of sorting a family of sets of uncertain elements admits a 2-round-competitive algorithm and this is the best possible.
Cite as

Thomas Erlebach, Michael Hoffmann, and Murilo Santos de Lima. Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.STACS.2021.27,
  author =	{Erlebach, Thomas and Hoffmann, Michael and de Lima, Murilo Santos},
  title =	{{Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.27},
  URN =		{urn:nbn:de:0030-drops-136728},
  doi =		{10.4230/LIPIcs.STACS.2021.27},
  annote =	{Keywords: online algorithms, competitive analysis, explorable uncertainty, parallel algorithms, minimum problem, selection problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.3
On Sorting with a Network of Two Stacks

Authors: Matúš Mihalák and Marc Pont

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
Sorting with stacks is a collection of problems that deal with sorting a sequence of numbers by pushing and popping the numbers to and from a given set of stacks. Multiple concrete decision or optimization questions are formed by restricting the access to the stacks. The motivation comes, e.g., from shunting train wagons in shunting yards, shunting trams in depots, or in stacking cargo containers on cargo ships or storage yards in transshipment terminals. We consider the problem of sorting a permutation of n integers 1,2,...,n using k >= 2 stacks. In this problem, elements from the input sequence are pushed one-by-one (in the order of the elements in the sequence) to one of the k stacks. At any time, an element from a stack can be popped and pushed to another stack; such an operation is called a shuffle. Also, at any time, an element can be popped from a stack and placed to the output sequence. We can only place the elements to the output in the increasing order of their value such that at the end the output is the ordered sequence of the elements. The problem asks to minimize the number of shuffles in the process. It is known that for k >= 4, the problem is NP-hard, and that there is no approximation algorithm unless P=NP. For k >= 3, it is known that at most O(n log n) shuffles are needed for any input sequence. For the case when k=2, there exist input sequences that require Omega(n^{2-epsilon}) shuffles, for any epsilon>0. Nothing substantially more is known for the case of k=2. In this paper, we study the following variant of the problem with k=2 stacks: no shuffle and no placement to the output sequence can happen before every element is in one of the two stacks. We show that our problem can be seen as the MinUnCut problem by providing a polynomial-time reduction, and thus we show that there exists a randomized O(sqrt{log n})-approximation algorithm and a deterministic O(log n)-approximation algorithm for our problem.
Cite as

Matúš Mihalák and Marc Pont. On Sorting with a Network of Two Stacks. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mihalak_et_al:OASIcs.ATMOS.2019.3,
  author =	{Mihal\'{a}k, Mat\'{u}\v{s} and Pont, Marc},
  title =	{{On Sorting with a Network of Two Stacks}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{3:1--3:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.3},
  URN =		{urn:nbn:de:0030-drops-114159},
  doi =		{10.4230/OASIcs.ATMOS.2019.3},
  annote =	{Keywords: Sorting, Stacks, Optimization, Algorithms, Reduction, MinUnCut}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.141
Two Moves per Time Step Make a Difference

Authors: Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n^{1.75}) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Omega(n^2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.
Cite as

Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner. Two Moves per Time Step Make a Difference. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.ICALP.2019.141,
  author =	{Erlebach, Thomas and Kammer, Frank and Luo, Kelin and Sajenko, Andrej and Spooner, Jakob T.},
  title =	{{Two Moves per Time Step Make a Difference}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{141:1--141:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.141},
  URN =		{urn:nbn:de:0030-drops-107176},
  doi =		{10.4230/LIPIcs.ICALP.2019.141},
  annote =	{Keywords: Temporal Graph Exploration, Algorithmic Graph Theory, NP-Complete Problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.51
Car-Sharing on a Star Network: On-Line Scheduling with k Servers

Authors: Kelin Luo, Thomas Erlebach, and Yinfeng Xu

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We study an on-line scheduling problem that is motivated by applications such as car-sharing for trips between an airport and a group of hotels. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit using k servers (cars). Each ride request specifies the pick-up time, the pick-up location, and the drop-off location, where one of the two locations must be the airport. A request must be submitted a fixed amount of time before the pick-up time. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). In the unit travel time variant, the travel time between the airport and any hotel is a fixed value t. We give a 2-competitive algorithm for the case in which the booking interval (pick-up time minus booking time) is at least t and the number of servers is even. In the arbitrary travel time variant, the travel time between the airport and a hotel may have arbitrary length between t and L t for some L >= 1. We give an algorithm with competitive ratio O(log L) if the number of servers is at least ceil[log L]. For both variants, we prove matching lower bounds on the competitive ratio of any deterministic on-line algorithm.
Cite as

Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing on a Star Network: On-Line Scheduling with k Servers. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.STACS.2019.51,
  author =	{Luo, Kelin and Erlebach, Thomas and Xu, Yinfeng},
  title =	{{Car-Sharing on a Star Network: On-Line Scheduling with k Servers}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.51},
  URN =		{urn:nbn:de:0030-drops-102907},
  doi =		{10.4230/LIPIcs.STACS.2019.51},
  annote =	{Keywords: Car-Sharing System, On-Line Scheduling, Competitive Analysis, Star Network}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.45
Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm

Authors: Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4k vectors into k quads with minimum total cost. We analyze a straightforward matching-based algorithm and prove that this algorithm is a 3/2-approximation algorithm for this problem. We further analyze the performance of this algorithm on a hierarchy of special cases of the problem and prove that, in one particular case, the algorithm is a 5/4-approximation algorithm. Our analysis is tight in all cases except one.
Cite as

Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma. Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ficker_et_al:LIPIcs.ISAAC.2018.45,
  author =	{Ficker, Annette M. C. and Erlebach, Thomas and Mihal\'{a}k, Mat\'{u}s and Spieksma, Frits C. R.},
  title =	{{Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{45:1--45:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.45},
  URN =		{urn:nbn:de:0030-drops-99933},
  doi =		{10.4230/LIPIcs.ISAAC.2018.45},
  annote =	{Keywords: approximation algorithm, matching, clustering problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.64
Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings

Authors: Kelin Luo, Thomas Erlebach, and Yinfeng Xu

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We study an on-line scheduling problem that is motivated by applications such as car-sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using k servers (cars). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). We consider two variants of the problem with respect to constraints on the booking time: In the fixed booking time variant, a request must be submitted a fixed amount of time before the pick-up time. In the variable booking time variant, a request can be submitted at any time during a certain time interval (called the booking horizon) that precedes the pick-up time. We present lower bounds on the competitive ratio for both variants and propose a balanced greedy algorithm (BGA) that achieves the best possible competitive ratio. We prove that, for the fixed booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the fixed booking length is not less than the travel time between the two locations; for the variable booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the length of the booking horizon is less than the travel time between the two locations, and BGA is 5/3-competitive if k=5i ( i in N) and the length of the booking horizon is not less than the travel time between the two locations.
Cite as

Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 64:1-64:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.ISAAC.2018.64,
  author =	{Luo, Kelin and Erlebach, Thomas and Xu, Yinfeng},
  title =	{{Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{64:1--64:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.64},
  URN =		{urn:nbn:de:0030-drops-100122},
  doi =		{10.4230/LIPIcs.ISAAC.2018.64},
  annote =	{Keywords: Car-sharing system, Competitive analysis, On-line scheduling}
}
  • Refine by Author
  • 20 Erlebach, Thomas
  • 5 Luo, Kelin
  • 3 Hoffmann, Michael
  • 3 Megow, Nicole
  • 3 Schöbel, Anita
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Design and analysis of algorithms
  • 3 Mathematics of computing → Discrete mathematics
  • 3 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Online algorithms
  • 2 Mathematics of computing → Approximation algorithms
  • Show More...

  • Refine by Keyword
  • 3 explorable uncertainty
  • 2 Car-sharing system
  • 2 Column Generation
  • 2 Competitive analysis
  • 2 On-line scheduling
  • Show More...

  • Refine by Type
  • 35 document
  • 1 volume

  • Refine by Publication Year
  • 15 2010
  • 5 2018
  • 4 2024
  • 3 2019
  • 3 2022
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact