Showing 2024Show all
3 papers · 1 filter
cs.DS2024
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…
cs.DS2024
Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
Evripidis Bampis, Konstantinos Dogeas, Thomas Erlebach +3
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…
cs.DS2024
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…