enter search term and/or author name
Approximation via cost sharing: Simpler and better approximation algorithms for network design
Anupam Gupta, Amit Kumar, Martin P´al, Tim Roughgarden
Article No.: 11
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 [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
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
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
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...