Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 55 Issue 6, December 2008

On the impact of combinatorial structure on congestion games
Heiner Ackermann, Heiko Röglin, Berthold Vöcking
Article No.: 25
DOI: 10.1145/1455248.1455249

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...

Linear-time disk-based implicit graph search
Richard E. Korf
Article No.: 26
DOI: 10.1145/1455248.1455250

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
DOI: 10.1145/1455248.1455251

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...

Weak ε-nets and interval chains
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
Article No.: 28
DOI: 10.1145/1455248.1455252

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...