Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 54 Issue 5, October 2007

AdWords and generalized online matching
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani
Article No.: 22
DOI: 10.1145/1284320.1284321

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP...

Low distortion embeddings for edit distance
Rafail Ostrovsky, Yuval Rabani
Article No.: 23
DOI: 10.1145/1284320.1284322

We show that {0, 1}d endowed with edit distance embeds into ℓ1 with distortion 2O(&sqrt;log d log log d). We further show efficient implementation of the embedding that...

On computing all abductive explanations from a propositional Horn theory
Thomas Eiter, Kazuhisa Makino
Article No.: 24
DOI: 10.1145/1284320.1284323

Abduction is a fundamental mode of reasoning with applications in many areas of AI and Computer Science. The computation of abductive explanations is an important computational problem, which is at the core of early systems such as the ATMS and...

Lossless abstraction of imperfect information games
Andrew Gilpin, Tuomas Sandholm
Article No.: 25
DOI: 10.1145/1284320.1284324

Finding an equilibrium of an extensive form game of imperfect information is a fundamental problem in computational game theory, but current techniques do not scale to large games. To address this, we introduce the ordered game isomorphism...

A bisimulation for type abstraction and recursion
Eijiro Sumii, Benjamin C. Pierce
Article No.: 26
DOI: 10.1145/1284320.1284325

We present a bisimulation method for proving the contextual equivalence of packages in λ-calculus with full existential and recursive types. Unlike traditional logical relations (either semantic or syntactic), our development is...