Search

Your search keyword '"Erlebach, Thomas"' showing total 29 results
Start Over Author "Erlebach, Thomas" Topic approximation algorithm

Refine your results

more »

more »

29 results on '"Erlebach, Thomas"'

1. A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs

Author

Erlebach, Thomas, Mihalák, Matúš, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bampis, Evripidis, editor, and Jansen, Klaus, editor

Published
2010
Full Text
View/download PDF

2. Domination in Geometric Intersection Graphs

Author

Erlebach, Thomas, van Leeuwen, Erik Jan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Laber, Eduardo Sany, editor, Bornstein, Claudson, editor, Nogueira, Loana Tito, editor, and Faria, Luerbio, editor

Published
2008
Full Text
View/download PDF

3. Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow

Author

Erlebach, Thomas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bampis, Evripidis, editor, Jansen, Klaus, editor, and Kenyon, Claire, editor

Published
2006
Full Text
View/download PDF

8. Package Delivery Using Drones with Restricted Movement Areas

Author

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

Subjects
FOS: Computer and information sciences, inapproximability, Theory of computation → Design and analysis of algorithms, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Mobile agents, approximation algorithm
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., LIPIcs, Vol. 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), pages 49:1-49:16

Published
2022
Full Text
View/download PDF

12. Complexity and online algorithms for minimum skyline coloring of intervals.

Author

Erlebach, Thomas, Liu, Fu-Hong, Liu, Hsiang-Hsuan, Shalom, Mordechai, Wong, Prudence W.H., and Zaks, Shmuel

Subjects
*COLORING matter, *ONLINE algorithms, *APPROXIMATION algorithms, *GRAPH coloring
Abstract

Motivated by applications in optical networks and job scheduling, we consider the interval coloring problem in a setting where an increasing cost is associated with using a higher color index. The cost of a coloring at any point of the line is the cost of the maximum color index used at that point, and the cost of the overall coloring is the integral of the cost over all points on the line. A coloring of minimum cost is called a minimum skyline coloring. We prove that the problem of computing a minimum skyline coloring is NP-hard and initiate the study of the online setting, where intervals arrive one by one. We give an asymptotically optimal online algorithm for the case of linear color costs and present further results for some variations and generalizations of the problem. Furthermore, we consider the variant of the minimum skyline coloring problem where the intervals are already partitioned into color classes and we only need permute the colors so as to minimize the cost of the coloring. We show that this problem variant is NP-hard and present a 2-approximation algorithm for it. [ABSTRACT FROM AUTHOR]

Published
2019
Full Text
View/download PDF

13. Scheduling parallel jobs with linear speedup

Author

Grigoriev, Alexander, Uetz, Marc, Erlebach, Thomas, Persinao, Giuseppe, and Discrete Mathematics and Mathematical Programming

Subjects
Mathematical optimization, Speedup, Job shop scheduling, Computer science, Approximation algorithm, Resource allocation, Quadratic programming, Integer programming, Time complexity, Computer Science::Operating Systems, Polynomial-time approximation scheme, Scheduling (computing)
Abstract

We consider a scheduling problem where a set of jobs is a-priori distributed over parallel machines. The processing time of any job is dependent on the usage of a scarce renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The dependence of processing times on the amount of resources is linear for any job. The objective is to find a resource allocation and a schedule that minimizes the makespan. Utilizing an integer quadratic programming relaxation, we show how to obtain a (3 + e) -approximation algorithm for that problem, for any e > 0. This generalizes and improves previous results, respectively. Our approach relies on a fully polynomial time approximation scheme to solve the quadratic programming relaxation. This result is interesting in itself, because the underlying quadratic program is NP-hard to solve. We also derive lower bounds, and discuss further generalizations of the results.

Published
2006

14. Maximising lifetime for fault-tolerant target coverage in sensor networks.

Author

Erlebach, Thomas, Grant, Tom, and Kammer, Frank

Subjects
FAULT-tolerant computing, SENSOR networks, APPROXIMATION algorithms, DYNAMIC programming, COMPUTER algorithms, GEOMETRIC analysis, GRAPH theory
Abstract

Abstract: We study the problem of maximising the lifetime of a sensor network for fault-tolerant target coverage in a setting with composite events. Here, a composite event is the simultaneous occurrence of a combination of atomic events, such as the detection of smoke and high temperature. We are given sensor nodes that have an initial battery level and can monitor certain event types, and a set of points at which composite events need to be detected. The points and sensor nodes are located in the Euclidean plane, and all nodes have the same sensing radius. The goal is to compute a longest activity schedule with the property that at any point in time, each event point is monitored by at least two active sensor nodes. We present a (6+ ɛ)-approximation algorithm for this problem by devising an approximation algorithm with the same ratio for the dual problem of minimising the weight of a fault-tolerant sensor cover. The algorithm generalises previous approximation algorithms for geometric set cover with weighted unit disks and is obtained by enumerating properties of the optimal solution that guide a dynamic programming approach. [Copyright &y& Elsevier]

Published
2011
Full Text
View/download PDF

15. Path problems in generalized stars, complete graphs, and brick wall graphs

Author

Erlebach, Thomas and Vukadinović, Danica

Subjects
*GRAPH theory, *ALGORITHMS, *FEASIBILITY studies, *OPTICAL communications
Abstract

Abstract: Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors. [Copyright &y& Elsevier]

Published
2006
Full Text
View/download PDF

16. Longest Increasing Subsequence Under Persistent Comparison Errors

Author

Geissmann, Barbara, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Epstein, Leah, editor, and Erlebach, Thomas, editor

Published
2018
Full Text
View/download PDF

17. Scheduling with an Orthogonal Resource Constraint

Author

Niemeier, Martin, Wiese, Andreas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Erlebach, Thomas, editor, and Persiano, Giuseppe, editor

Published
2013
Full Text
View/download PDF

18. A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs

Author

Bonsma, Paul, Zickfeld, Florian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Broersma, Hajo, editor, Erlebach, Thomas, editor, Friedetzky, Tom, editor, and Paulusma, Daniel, editor

Published
2008
Full Text
View/download PDF

19. Coping with Interference: From Maximum Coverage to Planning Cellular Networks

Author

Amzallag, David, Naor, Joseph (Seffi), Raz, Danny, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Erlebach, Thomas, editor, and Kaklamanis, Christos, editor

Published
2007
Full Text
View/download PDF

20. Approximation Algorithms for Multi-criteria Traveling Salesman Problems

Author

Manthey, Bodo, Ram, L. Shankar, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Erlebach, Thomas, editor, and Kaklamanis, Christos, editor

Published
2007
Full Text
View/download PDF

21. Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search

Author

Levin, Asaf, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Erlebach, Thomas, editor, and Kaklamanis, Christos, editor

Published
2007
Full Text
View/download PDF

22. Approximation Algorithms for Scheduling Problems with Exact Delays

Author

Ageev, Alexander A., Kononov, Alexander V., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Erlebach, Thomas, editor, and Kaklamanis, Christos, editor

Published
2007
Full Text
View/download PDF

23. Approximating Maximum Cut with Limited Unbalance

Author

Galbiati, Giulia, Maffioli, Francesco, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Erlebach, Thomas, editor, and Kaklamanis, Christos, editor

Published
2007
Full Text
View/download PDF

24. Reporting Flock Patterns

Author

Benkert, Marc, Gudmundsson, Joachim, Hübner, Florian, Wolle, Thomas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Azar, Yossi, editor, and Erlebach, Thomas, editor

Published
2006
Full Text
View/download PDF

25. Resource Allocation in Bounded Degree Trees

Author

Bar-Yehuda, Reuven, Beder, Michael, Cohen, Yuval, Rawitz, Dror, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Azar, Yossi, editor, and Erlebach, Thomas, editor

Published
2006
Full Text
View/download PDF

26. Greedy in Approximation Algorithms

Author

Mestre, Julián, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Azar, Yossi, editor, and Erlebach, Thomas, editor

Published
2006
Full Text
View/download PDF

27. Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT

Author

Avidor, Adi, Berkovitch, Ido, Zwick, Uri, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Erlebach, Thomas, editor, and Persinao, Giuseppe, editor

Published
2006
Full Text
View/download PDF

28. On Approximating Restricted Cycle Covers

Author

Manthey, Bodo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Erlebach, Thomas, editor, and Persinao, Giuseppe, editor

Published
2006
Full Text
View/download PDF

29. Longest Increasing Subsequence Under Persistent Comparison Errors

Author

Barbara Geissmann, Epstein, Leah, and Erlebach, Thomas

Subjects
FOS: Computer and information sciences, Sequence, 0211 other engineering and technologies, Sorting, Approximation algorithm, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, Longest increasing subsequence, 01 natural sciences, Theoretical Computer Science, Combinatorics, Probabilistic persistent comparison errors, Lower bounds, Computational Theory and Mathematics, 010201 computation theory & mathematics, Resampling, Theory of computation, Computer Science - Data Structures and Algorithms, Subsequence, Data Structures and Algorithms (cs.DS), Mathematics, Sequence (medicine)
Abstract

We study the problem of computing a longest increasing subsequence in a sequence $S$ of $n$ distinct elements in the presence of persistent comparison errors. In this model, every comparison between two elements can return the wrong result with some fixed (small) probability $ p $, and comparisons cannot be repeated. Computing the longest increasing subsequence exactly is impossible in this model, therefore, the objective is to identify a subsequence that (i) is indeed increasing and (ii) has a length that approximates the length of the longest increasing subsequence. We present asymptotically tight upper and lower bounds on both the approximation factor and the running time. In particular, we present an algorithm that computes an $O(\log n)$-approximation in time $O(n\log n)$, with high probability. This approximation relies on the fact that that we can approximately sort $n$ elements in $O(n\log n)$ time such that the maximum dislocation of an element is at most $O(\log n)$. For the lower bounds, we prove that (i) there is a set of sequences, such that on a sequence picked randomly from this set every algorithm must return an $\Omega(\log n)$-approximation with high probability, and (ii) any $O(\log n)$-approximation algorithm for longest increasing subsequence requires $\Omega(n \log n)$ comparisons, even in the absence of errors.

Published
2018

Catalog

Books, media, physical & digital resources
See catalog results