enter search term and/or author name
On the impact of combinatorial structure on congestion games
Heiner Ackermann, Heiko Röglin, Berthold Vöcking
Article No.: 25
We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of...
Many search algorithms are limited by the amount of memory available. Magnetic disk storage is over two orders of magnitude cheaper than semiconductor memory, and individual disks can hold up to a terabyte. We augment memory with magnetic disks to...
Almost-tight hardness of directed congestion minimization
Matthew Andrews, Lisa Zhang
Article No.: 27
Given a set of demands in a directed graph, the directed congestion minimization problem is to route every demand with the objective of minimizing the heaviest load over all edges. We show that for any constant ϵ > 0, there is no...
We construct weak ε-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1/r-nets of size O(rα(r)), where α(r) denotes the inverse Ackermann...