Bremen Day of Combinatorial Optimization

Approximate Flows and Allocations

February 21, 2023
University of Bremen, Cartesium, Rotunde
Enrique-Schmidt-Straße 5, 28359 Bremen
 

Program
11:30  – 12:15 Sven Krumke (U Kaiserslautern): Approximation Schemes for Fractional Flow and Packing Problems Lunch (Cafe Unique or Mensa)
13:30 – 14:00 Franziska Eberle (LSE London): Stochastic Configuration Balancing
14:00 – 14:30 Daniel Schmand (U Bremen): Bicriteria Nash Flows over Time Coffee Break in MZH 3200
16:00 Lukas Nölke (PhD Defense): Matching and Packing Problems – Optimization Under Uncertainty in Theory and Practice

In case you would like to participate online then please write an email to Lukas Barning

Abstracts

Sven Krumke: Approximation Schemes for Fractional Flow and Packing Problems

A fractional packing problem is an optimization problem of the form max {c^T x : Ax\leq b, x\geq 0}, where A is a matrix with nonnegative entries. Numerous problems in the field of network flows, among others, can be formulated this way. Garg and Koenemann (2007) have presented a general concept to obtain polynomial-time approximation schemes (FPTAS) for such packing problems: for given accuracy \epsilon>0, the algorithm finds in time polynomial in the input size and 1/\varepsilon a solution that has value at least (1-\varepsilon) times that of the optimal solution.

We present a generalization of the concept of Garg and Koememann. Given is a polyhedral cone C generated by a finite (possibly exponentially large) set S of non-negative vectors (one trivial example is the nonnegative orthant). The central packing problem is then max { c^T x : Ax\leq b, x\in C }. Instead of assuming that the cone C is explicitly given, we only assume that we can access the cone via three types of "oracles". The strongest oracle (called minimization oracle) returns, for a given objective function vector d, a vector x\in C that minimizes d^T x. The other oracles (sign oracle and separation oracle) are weaker and provide less information.

Our central result is that one can obtain fully polynomial approximation schemes over these polyhedral cones using each of the oracles in a generic way. As applications, numerous approximation results arise for, among others:
- budget-constrained maximum flows
- budget-constrained cost-minimal flows
- restricted generalized flows (i.e. flows with gains and losses on the edges)
- restricted flows in process networks
- Packing of spanning trees or bases in matroids.
The techniques we use include Megiddo's parametric search and various acceleration techniques.

Our algorithms are either the first approximation schemes or improve on previously known results from the literature. Although the central result sounds very theoretical (and potentially esoteric) at first, it has strong practical implications: the basic algorithm is surprisingly simple and also easy to implement, especially if one uses a modern object-oriented programming language.

Franziska Eberle: Stochastic Configuration Balancing

The configuration balancing problem with stochastic requests generalizes many well-studied resource allocation problems such as load balancing and virtual circuit routing. In it, we have m resources and n requests. Each request has multiple possible configurations, each of which increases the load of each resource by some amount. The goal is to select one configuration for each request to minimize the makespan: the load of the most-loaded resource. In our work, we focus on a stochastic setting, where we only know the distribution for how each configuration increases the resource loads, learning the realized value only after a configuration is chosen.We develop

both offline and online algorithms for configuration balancing with stochastic requests. When the requests are known offline, we give a non-adaptive policy for configuration balancing with stochastic requests that O(log m / log log m)-approximates the optimal adaptive policy. In particular, this closes the adaptivity gap for this problem as there is an asymptotically matching lower bound even for the very special case of load balancing on identical machines. When requests arrive online in a list, we give a non-adaptive policy that is O(log m) competitive. Again, this result is asymptotically tight due to information-theoretic lower bounds for very special cases (e.g., for load balancing on unrelated machines). Finally, we show how to leverage adaptivity in the special case of load balancing on related machines to obtain a constant-factor approximation offline and an O(log log m)- approximation online. A crucial technical ingredient in all of our results is a new structural characterization of the optimal adaptive policy that allows us to limit the correlations between its decisions.
This is joint work with Anupam Gupta, Nicole Megow, Ben Moseley, and Rudy Zhou, IPCO 2023.

Daniel Schmand: Bicriteria Nash Flows over Time

Flows over time are a natural way to incorporate flow dynamics that arise in various applications such as traffic networks. In this paper we introduce a natural variant of the deterministic fluid queuing model in which users aim to minimize their costs subject to arrival at their destination before a pre-specified deadline. We determine the existence and the structure of Nash flows over time and fully characterize the price of anarchy for this model. The price of anarchy measures the ratio of the quality of the equilibrium and the quality of the optimum flow, where we evaluate the quality using two different natural performance measures: the throughput for a given deadline and the makespan for a given amount of flow. While it turns out that both prices of anarchy can be unbounded in general, we provide tight bounds for the important subclass of parallel path networks. Surprisingly, the two performance measures yield different results here.
This is joint work with Tim Oosterwijk and Marc Schröder.