Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 49 Issue 5, September 2002

Truth revelation in approximately efficient combinatorial auctions
Daniel Lehmann, Liadan Ita Oćallaghan, Yoav Shoham
Pages: 577-602
DOI: 10.1145/585265.585266
Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance,...

The greedy path-merging algorithm for contig scaffolding
Daniel H. Huson, Knut Reinert, Eugene W. Myers
Pages: 603-615
DOI: 10.1145/585265.585267
Given a collection of contigs and mate-pairs. The Contig Scaffolding Problem is to order and orientate the given contigs in a manner that is consistent with as many mate-pairs as possible. This paper describes an efficient heuristic called the...

Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields
Jon Kleinberg, Éva Tardos
Pages: 616-639
DOI: 10.1145/585265.585268
In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is...

On the online bin packing problem
Steven S. Seiden
Pages: 640-671
DOI: 10.1145/585265.585269
A new framework for analyzing online bin packing algorithms is presented. This framework presents a unified way of explaining the performance of algorithms based on the Harmonic approach. Within this framework, it is shown that a new algorithm,...

Alternating-time temporal logic
Rajeev Alur, Thomas A. Henzinger, Orna Kupferman
Pages: 672-713
DOI: 10.1145/585265.585270
Temporal logic comes in two varieties: linear-time temporal logic assumes implicit universal quantification over all paths that are generated by the execution of a system; branching-time temporal logic allows explicit existential and...