Approximation Algorithms for Unsplittable Resource Allocation Problems


In this project we study general resource allocation problems with a diseconomy of scale. In such problems, we are given a finite set of commodities that request certain resources. The cost of each resource grows superlinearly with the demand for it, and our goal is to minimize the total cost of the resources. These unsplittable resource allocation problems naturally appear in different areas. Examples include the energy minimization of computing devices
or the travel time minimization on roads amenable to congestion.

An important special case of the resource allocation problems considered in this work are network flow problems, where we have to allocate exactly one path to each commodity with a designated start and target node. In this case, the resource allocation problem is equivalent to computing a cost minimal unsplittable flow without capacity constraints and with convex costs.

The best known polynomial time approximation algorithm for these problems is due to Makarychev and Srividenko [FOCS 2014]. Their algorithm is based on the randomized rounding of the solution of a convex programming relaxation. We aim to find and analyse very simple, deterministic and combinatorial algorithms that also work in the online setting. Here, commodities show up one after each other and we immediately have to assign certain resources to them, without knowing how many or which additional commodities may also be there. A good starting point for the online problem are greedy algorithms, where local search algorithms may work in the offline setting.

This project is contributed by Antje Bjelde, Max Klimm, Daniel Schmand, and Andreas Tönnis.

See also:

Bjelde, Klimm, Schmand: Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale
in Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2017)