Skip to main content

Research Repository

Advanced Search

All Outputs (19)

Classification and evaluation of the algorithms for vector bin packing (2024)
Journal Article
Mommessin, C., Erlebach, T., & Shakhlevich, N. V. (2025). Classification and evaluation of the algorithms for vector bin packing. Computers and Operations Research, 173, Article 106860. https://doi.org/10.1016/j.cor.2024.106860

Heuristics for Vector Bin Packing (VBP) play an important role in modern distributed computing systems and other applications aimed at optimizing the usage of multidimensional resources. In this paper we perform a systematic classification of heurist... Read More about Classification and evaluation of the algorithms for vector bin packing.

Scheduling with Obligatory Tests (2024)
Presentation / Conference Contribution
Dogeas, K., Erlebach, T., & Liang, Y.-C. (2024, September). Scheduling with Obligatory Tests. Presented at 32nd Annual European Symposium on Algorithms (ESA 2024), Egham, United Kingdom

Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations, a test and a processing part. The time required to execute the test is known in advance while the tim... Read More about Scheduling with Obligatory Tests.

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty (2024)
Presentation / Conference Contribution
Bampis, E., Dogeas, K., Erlebach, T., Megow, N., Schlöter, J., & Trehan, A. (2024, August). Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. Presented at International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024), London, UK

We study the two-sided stable matching problem with one-sided uncertainty for two sets of agents A and B, with equal cardinality. Initially, the preference lists of the agents in A are given but the preferences of the agents in B are unknown. An algo... Read More about Competitive Query Minimization for Stable Matching with One-Sided Uncertainty.

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous (2024)
Presentation / Conference Contribution
Dogeas, K., Erlebach, T., Kammer, F., Meintrup, J., & Moses Jr, W. K. (2024, July). Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. Presented at 51st EATCS International Colloquium on Automata, Languages and Programming, Tallinn, Estonia

Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization (2024)
Presentation / Conference Contribution
Erlebach, T., Morawietz, N., & Wolf, P. (2024, June). Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. Presented at 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), Patras, Greece

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... Read More about Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization.

Sorting and Hypergraph Orientation under Uncertainty with Predictions (2023)
Presentation / Conference Contribution
Erlebach, T., de Lima, M., Megow, N., & Schlöter, J. (2023, August). Sorting and Hypergraph Orientation under Uncertainty with Predictions. Presented at Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023), Macao, S.A.R., China

Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of uncertain input elements can be obtained by a query and the goal is to min... Read More about Sorting and Hypergraph Orientation under Uncertainty with Predictions.

List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs (2023)
Presentation / Conference Contribution
Baklan Sen, B., Diner, Ö. Y., & Erlebach, T. (2023, December). List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs. Presented at 29th International Computing and Combinatorics Conference (COCOON 2023), Honolulu, Hawaii, USA

Given a graph G = (V, E) and a list of available colors L(v) for each vertex v ∈ V, where L(v) ⊆ {1, 2, . . . , k}, LIST k-COLORING refers to the problem of assigning colors to the vertices of G so that each vertex receives a color from its own list... Read More about List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs.

Parameterized temporal exploration problems (2023)
Journal Article
Erlebach, T., & Spooner, J. T. (2023). Parameterized temporal exploration problems. Journal of Computer and System Sciences, 135, 73-88. https://doi.org/10.1016/j.jcss.2023.01.003

In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph G admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices.... Read More about Parameterized temporal exploration problems.

Package Delivery Using Drones with Restricted Movement Areas (2022)
Presentation / Conference Contribution
Erlebach, T., Luo, K., & Spieksma, F. C. (2022, December). Package Delivery Using Drones with Restricted Movement Areas. Presented at 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Seoul, Korea

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty (2022)
Presentation / Conference Contribution
Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2022, September). Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. Presented at 30th Annual European Symposium on Algorithms (ESA 2022), Potsdam, Germany

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 fundam... Read More about Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty.

Round-competitive algorithms for uncertainty problems with parallel queries (2022)
Journal Article
Erlebach, T., Hoffmann, M., & de Lima, M. S. (2023). Round-competitive algorithms for uncertainty problems with parallel queries. Algorithmica, 85(2), 406-443. https://doi.org/10.1007/s00453-022-01035-6

In computing with explorable uncertainty, one considers problems where the values of some input elements are uncertain, typically represented as intervals, but can be obtained using queries. Previous work has considered query minimization in the sett... Read More about Round-competitive algorithms for uncertainty problems with parallel queries.

Exploration of k-Edge-Deficient Temporal Graphs (2022)
Journal Article
Erlebach, T., & Spooner, J. T. (2022). Exploration of k-Edge-Deficient Temporal Graphs. Acta Informatica, 59(4), 387-407. https://doi.org/10.1007/s00236-022-00421-5

A temporal graph with lifetime L is a sequence of L graphs G1, . . . , GL, called layers, all of which have the same vertex set V but can have different edge sets. The underlying graph is the graph with vertex set V that contains all the edges that a... Read More about Exploration of k-Edge-Deficient Temporal Graphs.

Parameterized temporal exploration problems (2022)
Presentation / Conference Contribution
Erlebach, T., & Spooner, J. T. (2022, March). Parameterized temporal exploration problems. Presented at 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), Virtual Conference

In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph G admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices.... Read More about Parameterized temporal exploration problems.

Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings (2022)
Journal Article
Luo, K., Erlebach, T., & Xu, Y. (2022). Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings. Discrete Applied Mathematics, 313, 53-66. https://doi.org/10.1016/j.dam.2022.01.016

We study an online scheduling problem that is motivated by applications such as car-sharing. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit using a single server (car). Each ride request specifies the pi... Read More about Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings.

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty (2021)
Presentation / Conference Contribution
Bampis, E., Dürr, C., Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2021, December). Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. Presented at 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon, Portugal (Virtual Conference)

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... Read More about Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty.

Exploration of k-Edge-Deficient Temporal Graphs (2021)
Presentation / Conference Contribution
Erlebach, T., & Spooner, J. T. (2021, December). Exploration of k-Edge-Deficient Temporal Graphs. Presented at WADS 2021: Algorithms and Data Structures

Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries (2021)
Presentation / Conference Contribution
Erlebach, T., Hoffmann, M., & de Lima, M. S. (2021, December). Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. Presented at 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Saarbrücken, Germany