5 papers
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
Haya Diwan, Lisa Hellerstein, Nicole Megow +1
Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values o…
Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
Alexander Lindermayr, Zhenwei Liu, Nicole Megow
We propose new abstract and unified perspectives on a range of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider various problems wh…
Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
Felix Hommelsheim, Zhenwei Liu, Nicole Megow +1
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, whi…
The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints
Sven Jäger, Alexander Lindermayr, Nicole Megow
The Polytope Scheduling Problem (PSP) was introduced by Im, Kulkarni, and Munagala (JACM 2018) as a very general abstraction of resource allocation over time and captures many well…
Accelerating Matroid Optimization through Fast Imprecise Oracles
Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr +3
Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus…