Publications related to Fully dynamic bin packing revisited

Approximation Algorithms for Allocation and Network Design

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

The end of urban sprawl? Internal migration across the rural-urban continuum in Switzerland, 1966-2018

Mathias Lerch

In high-income countries, migration redistributed populations from congested city centres into the sparsely populated outskirts, raising challenges to environmental and population health and the conservation of biodiversity. We evaluate whether this periur ...

WILEY2022

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

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Boi Faltings, Aris Filos Ratsikas, Panayiotis Danassis

We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on th ...

2019

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] ...

Assoc Computing Machinery2016

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Association for Computing Machinery2013

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [1] pro ...

Springer2012

New Results in the Theory of Linear and Integer Programming

Nicolai Hähnle

The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...

EPFL2012

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling

Thomas Rothvoss

We introduce the "First Fit Matching Periods" algorithm for static-priority multiprocessor scheduling of periodic tasks with implicit deadlines and show that it yields asymptotically optimal processor assignments if utilization values are chosen uniformly ...

Springer2009

Fully dynamic bin packing revisited

Graph Chatbot

Chat with Graph Search

Approximation Algorithms for Allocation and Network Design

The double exponential runtime is tight for 2-stage stochastic ILPs

The end of urban sprawl? Internal migration across the rural-urban continuum in Switzerland, 1966-2018

New Results in Integer and Lattice Programming

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Bin Packing via Discrepancy of Permutations

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation

New Results in the Theory of Linear and Integer Programming

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling

Approximation Algorithms for Allocation and Network Design

New Results in Integer and Lattice Programming

The double exponential runtime is tight for 2-stage stochastic ILPs

Bin Packing via Discrepancy of Permutations

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

New Results in the Theory of Linear and Integer Programming

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

The end of urban sprawl? Internal migration across the rural-urban continuum in Switzerland, 1966-2018

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation