12 citations · 42 across the 15 of their papers we have counts for
21 papers
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…
A Simplified Analysis of the Ascending Auction to Sell a Matroid Base
Britta Peis, Niklas Rieken
We give a simpler analysis of the ascending auction of Bikhchandani, de Vries, Schummer, and Vohra to sell a welfare-maximizing base of a matroid at Vickrey prices. The new proofs…
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…
Recoverable Robust Optimization with Commitment
Felix Hommelsheim, Nicole Megow, Komal Muluk +1
We propose a model for recoverable robust optimization with commitment. Given a combinatorial optimization problem and uncertainty about elements that may fail, we ask for a robust…
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…
A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
S. Thomas McCormick, Britta Peis, Robert Scheidweiler +1
In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i…
Matroid Bases with Cardinality Constraints on the Intersection
Stefan Lendl, Britta Peis, Veerle Timmermans
Given two matroids and on a common ground set with base sets and $\mathcal{B…
Computational Methods for Path-based Robust Flows
Fabian Mies, Britta Peis, Andreas Wierz
Real world networks are often subject to severe uncertainties which need to be addressed by any reliable prescriptive model. In the context of the maximum flow problem subject to a…
The Primal-Dual Greedy Algorithm for Weighted Covering Problems
Britta Peis, José Verschae, Andreas Wierz
We present a general approximation framework for weighted integer covering problems. In a weighted integer covering problem, the goal is to determine a non-negative integer solutio…
Sensitivity Analysis for Convex Separable Optimization over Integral Polymatroids
Tobias Harks, Max Klimm, Britta Peis
We study the sensitivity of optimal solutions of convex separable optimization problems over an integral polymatroid base polytope with respect to parameters determining both the c…
Additive Stabilizers for Unstable Graphs
Karthekeyan Chandrasekaran, Corinna Gottschalk, Jochen Könemann +3
Stabilization of graphs has received substantial attention in recent years due to its connection to game theory. Stable graphs are exactly the graphs inducing a matching game with…
Robust Flows over Time: Models and Complexity Results
Corinna Gottschalk, Arie M. C. A. Koster, Frauke Liers +3
We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the…
Protection of flows under targeted attacks
Jannik Matuschke, S. Thomas McCormick, Gianpaolo Oriolo +2
Due to the importance of robustness in many real-world optimization problems, the field of robust optimization has gained a lot of attention over the past decade. We concentrate on…
Submodular Function Maximization over Distributive and Integer Lattices
Corinna Gottschalk, Britta Peis
The problem of maximizing non-negative submodular functions has been studied extensively in the last few years. However, most papers consider submodular set functions. Recently, se…
Matroids are Immune to Braess Paradox
Satoru Fujishige, Michel X. Goemans, Tobias Harks +2
The famous Braess paradox describes the following phenomenon: It might happen that the improvement of resources, like building a new street within a congested network, may in fact…
Resource Competition on Integral Polymatroids
Tobias Harks, Max Klimm, Britta Peis
We study competitive resource allocation problems in which players distribute their demands integrally on a set of resources subject to player-specific submodular capacity constrai…
Abstract flows over time: A first step towards solving dynamic packing problems
Jan-Philipp W. Kappmeier, Jannik Matuschke, Britta Peis
Flows over time generalize classical network flows by introducing a notion of time. Each arc is equipped with a transit time that specifies how long flow takes to traverse it, whil…
Lattices and maximum flow algorithms in planar graphs
Jannik Matuschke, Britta Peis
We show that the left/right relation on the set of s-t-paths of a plane graph induces a so-called submodular lattice. If the embedding of the graph is s-t-planar, this lattice is e…
Max-Flow on Regular Spaces
Ulrich Faigle, Walter Kern, Britta Peis
The max-flow and max-coflow problem on directed graphs is studied in the common generalization to regular spaces, i.e., to kernels or row spaces of totally unimodular matrices. Exh…
Resource Buying Games
Tobias Harks, Britta Peis
In resource buying games a set of players jointly buys a subset of a finite resource set E (e.g., machines, edges, or nodes in a digraph). The cost of a resource e depends on the n…
On Generalizations of Network Design Problems with Degree Bounds
Nikhil Bansal, Rohit Khandekar, Jochen Konemann +2
Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope…