Publications related to Approximation Algorithms for Allocation and Network Design

Knapsack and Subset Sum with Small Items

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Friedrich Eisenbrand, Moritz Andreas Venzin, Jana Tabea Cslovjecsek

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

Maryam Kamgarpour, Orcun Karaca

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and ...

2021

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...

2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

A note on the integrality gap of the configuration LP for restricted Santa Claus

Klaus Jansen, Lars Rohwedder

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to pl ...

ELSEVIER2020

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

Boi Faltings, Panayiotis Danassis

The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the f ...

IOS PRESS2020

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Mika Tapani Göös

We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2020

Interpolatory Rational Model Order Reduction of Parametric Problems Lacking Uniform Inf-Sup Stability

Davide Pradovera

We present a technique for the approximation of a class of Hilbert space--valued maps which arise within the framework of model order reduction (MOR) for parametric partial differential equations, whose solution map has a meromorphic structure. Our MOR str ...

2020

Fully dynamic bin packing revisited

Kim-Manuel Klein, Klaus Jansen

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. ...

SPRINGER HEIDELBERG2020

Approximation Algorithms for Allocation and Network Design

Graph Chatbot

Chat with Graph Search

Knapsack and Subset Sum with Small Items

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

New Results in Integer and Lattice Programming

A note on the integrality gap of the configuration LP for restricted Santa Claus

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Interpolatory Rational Model Order Reduction of Parametric Problems Lacking Uniform Inf-Sup Stability

Fully dynamic bin packing revisited

Knapsack and Subset Sum with Small Items

New Results in Integer and Lattice Programming

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

A note on the integrality gap of the configuration LP for restricted Santa Claus

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Interpolatory Rational Model Order Reduction of Parametric Problems Lacking Uniform Inf-Sup Stability

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

Fully dynamic bin packing revisited