Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 53 Issue 5, September 2006

New hardness results for congestion minimization and machine scheduling
Julia Chuzhoy, Joseph (Seffi) Naor
Pages: 707-721
DOI: 10.1145/1183907.1183908
We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. In this problem, we are given a directed graph and a set of source-sink pairs. The goal is to route all the pairs...

Finding a maximum likelihood tree is hard
Benny Chor, Tamir Tuller
Pages: 722-744
DOI: 10.1145/1183907.1183909
Maximum likelihood (ML) is an increasingly popular optimality criterion for selecting evolutionary trees [Felsenstein 1981]. Finding optimal ML trees appears to be a very hard computational task, but for tractable cases, ML is the method of choice....

Logarithmic hardness of the undirected edge-disjoint paths problem
Matthew Andrews, Lisa Zhang
Pages: 745-761
DOI: 10.1145/1183907.1183910
We show that there is no log⅓ − ϵ M approximation for the undirected Edge-Disjoint Paths problem unless NPZPTIME(npolylog(n)), where M is the size of the graph...

Combining expert advice in reactive environments
Daniela Pucci De Farias, Nimrod Megiddo
Pages: 762-799
DOI: 10.1145/1183907.1183911
“Experts algorithms” constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of...

Using expander graphs to find vertex connectivity
Harold N. Gabow
Pages: 800-844
DOI: 10.1145/1183907.1183912
The (vertex) connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding κ. For a digraph with n vertices, m edges...

Online algorithms for market clearing
Avrim Blum, Tuomas Sandholm, Martin Zinkevich
Pages: 845-879
DOI: 10.1145/1183907.1183913
In this article, we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire at different times. The auctioneer is faced with an online...