Skip to main content

Research Repository

Advanced Search

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.

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.