Combinatorial Optimization and Logistics
The Combinatorial Optimization and Logistics (CSLog) group at the University of Bremen focuses on the analysis of discrete algorithmic problems that are computationally difficult. We analyze the structure of such problems and design efficient algorithms with provable performance guarantees for solving them. We are also interested in combinatorial optimization problems where the input is revealed only incrementally or where there is uncertainty in the parameters, and we develop online, stochastic or robust solution methods.
Combinatorial optimization is related to theoretical computer science, discrete mathematics, operations research, algorithm theory and computational complexity theory and has important applications in several fields. In our group we develop theoretic results and apply them to complex real-world environments. Typical applications include scheduling, production planning, logistics, network design, communication and routing in networks, and health care.
Combinatorial Optimization and Logistics
Faculty 3 - Mathematics and Computer Science
Prof. Dr. Nicole Megow
Telefon: +49 (0) 421 218 63580
Open Source Project
Website on Algorithms with Predictions
April 25, 2023: Our paper "Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary" (Alexander Lindermayr, Nicole Megow, Martin Rapp) got accepted at ICML 2023.
April 25, 2023: Our paper "Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints" (Alexandra Lassota, Alexander Lindermayr, Nicole Megow, Jens Schlöter) got accepted at ICML 2023.
April 24, 2023: Nicole is co-organizer of the ICALP 2023 Satellite Workshop: Workshop on Recent Trends in Online Algorithms (with Thomas Erlebach, Kazuo Iwama, Chung-Shou Liao). Please consider to participate!
April 21, 2023: Our paper "Matching Augmentation via Simultaneous Contractions" (Mohit Garg, Felix Hommelsheim, Nicole Megow) got accepted at ICALP 2023.
April 20, 2023: Our Paper "Sorting and Hypergraph Orientation under Uncertainty with Predictions" (Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter) got accepted at IJCAI 2023 (acceptance rate 15%).
April 5, 2023: Nicole is the PC chair of APPROX 2023. Please consider submitting. Deadline is May 5.
Feb 21, 2023: We are hosting the Bremen Day on Combinatorial Optimization: Approximate Flows and Allocations with talks by Sven Krumke (Kaiserslautern), Franziska Eberle (London), Daniel Schmand (Bremen) and the PhD Defense of Lukas Nölke. More details here
Feb 5-10, 2023: We are having a great time at the wonderful Dagstuhl Seminar 23061 on Scheduling with a focus on beyond-worst case analysis, learning, and stochastic models.
Feb 1, 2023: The full version of our paper "Speed-robust scheduling: sand, bricks, and rocks" (Eberle, Hoeksma, Megow, Nölke, Schewior, Simon) appeared in Mathematical Programming.
Jan 20, 2023: Our paper "Set Selection under Explorable Stochastic Uncertainty via Covering Techniques" has been accepted at IPCO 2023.
Jan 20, 2023: Our paper "Configuration Balancing for Stochastic Requests" has been accepted at IPCO 2023.
Oct 15, 2022: Our group (Alex, Jens, Nicole) participated in Campus City with puzzles on combinatorics and optimization in a joint event of Faculty 3 optimization research groups in Überseemuseum.
Oct 10, 2022: Theophile Thiery from Queen Mary University, London, is visiting us for a month. Welcome!
Sep 15, 2022: Our paper "A Universal Error Measure for Input Predictions Applied to Online Graph Problems" has been accepted at NeurIPS 2022.
Jun 20, 2022: Our paper "Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty" has been accepted at ESA 2022.
Jun 18, 2022: Alexander Lindermayr receives the Faculty Award 2022 for his Master Thesis on "Learning-Augmented Online Algorithms for the 2-Server Problem on the Line and Generalizations". Congratulations!
Jun 12-17, 2022: Our (former) group members give four talks at MAPSP 2022 in Oropa, Italy.
Jun 8, 2022: Nicole Megow gives a keynote talk on "Learning-Augmented Online Algorithms for Scheduling and Routing" in the Online Scheduling Seminar
May 10, 2022: Our paper "Non-clairvoyant Scheduling with Predictions Revisited" has been accepted at SPAA 2022.
May 8, 2022: We launched the open source project https://algorithms-with-predictions.github.io/ with a collection on papers, workshops etc. around algorithms with predictions.
May 3, 2022: Nicole Megow gives an invited lecture on "Online Routing and Network Design with Predictions" at the Workshop on Algorithms with Predictions (ALPS) at Bernoulli Center, EPFL.
Apr 10, 2022: Our paper "Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults" has been accepted at SWAT 2022.