3 papers
cs.DS2025
On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
Umang Bhaskar, Katharina Eickhoff, Lennart Kauther +3
In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requi…
cs.GT2024
Faster Dynamic Auctions via Polymatroid Sum
Katharina Eickhoff, Meike Neuwohner, Britta Peis +3
We consider dynamic auctions for finding Walrasian equilibria in markets with indivisible items and strong gross substitutes valuation functions. Each price adjustment step in thes…
cs.GT2024
A flow-based ascending auction to compute buyer-optimal Walrasian prices
Katharina Eickhoff, S. Thomas McCormick, Britta Peis +2
We consider a market where a set of objects is sold to a set of buyers, each equipped with a valuation function for the objects. The goal of the auctioneer is to determine reasonab…