Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 54 Issue 3, June 2007

Approximation via cost sharing: Simpler and better approximation algorithms for network design
Anupam Gupta, Amit Kumar, Martin P´al, Tim Roughgarden
Article No.: 11
DOI: 10.1145/1236457.1236458

We present constant-factor approximation algorithms for several widely-studied NP-hard optimization problems in network design, including the multicommodity rent-or-buy, virtual private network design, and single-sink buy-at-bulk problems. Our...

The PCP theorem by gap amplification
Irit Dinur
Article No.: 12
DOI: 10.1145/1236457.1236459

The PCP theorem [Arora and Safra 1998; Arora et. al. 1998] says that every language in NP has a witness format that can be checked probabilistically by reading only a constant number of bits from the proof. The celebrated equivalence of this...

Dynamic ordered sets with exponential search trees
Arne Andersson, Mikkel Thorup
Article No.: 13
DOI: 10.1145/1236457.1236460

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures.

This leads to an optimal bound of...

When are elections with few candidates hard to manipulate?
Vincent Conitzer, Tuomas Sandholm, Jérôme Lang
Article No.: 14
DOI: 10.1145/1236457.1236461

In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable....

Characterizing and reasoning about probabilistic and non-probabilistic expectation
Joseph Y. Halpern, Riccardo Pucella
Article No.: 15
DOI: 10.1145/1236457.1236462

Expectation is a central notion in probability theory. The notion of expectation also makes sense for other notions of uncertainty. We introduce a propositional logic for reasoning about expectation, where the semantics depends on the underlying...