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
Outputs (12)
Scheduling with Obligatory Tests (2024)
Presentation / Conference Contribution
Dogeas, K., Erlebach, T., & Liang, Y.-C. (2024, September). Scheduling with Obligatory Tests. Paper presented at 32nd Annual European Symposium on Algorithms (ESA 2024), Egham, United Kingdom
Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization (2024)
Presentation / Conference Contribution
Erlebach, T., Morawietz, N., & Wolf, P. (2024). Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. In Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (12:1-12:16). https://doi.org/10.4230/LIPIcs.SAND.2024.12
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. (in press). Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (62:1-62:19). https://doi.org/10.4230/LIPIcs.ICALP.2024.62
Sorting and Hypergraph Orientation under Uncertainty with Predictions (2023)
Presentation / Conference Contribution
Erlebach, T., de Lima, M., Megow, N., & Schlöter, J. (2023). Sorting and Hypergraph Orientation under Uncertainty with Predictions. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (5577-5585). https://doi.org/10.24963/ijcai.2023/619Learning-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, USAGiven 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.
Package Delivery Using Drones with Restricted Movement Areas (2022)
Presentation / Conference Contribution
Erlebach, T., Luo, K., & Spieksma, F. C. (in press). Package Delivery Using Drones with Restricted Movement Areas. In S. W. Bae, & H. Park (Eds.), . https://doi.org/10.4230/lipics.isaac.2022.49
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). Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms (ESA 2022) (12:1-12:16). https://doi.org/10.4230/lipics.esa.2022.12We 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.
Parameterized temporal exploration problems (2022)
Presentation / Conference Contribution
Erlebach, T., & Spooner, J. T. (2022). Parameterized temporal exploration problems. In J. Aspnes, & O. Michail (Eds.), . https://doi.org/10.4230/lipics.sand.2022.15In 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.
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). Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. . https://doi.org/10.4230/lipics.esa.2021.10Given 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). Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. . https://doi.org/10.4230/lipics.stacs.2021.27