enter search term and/or author name
Truth revelation in approximately efficient combinatorial auctions
Daniel Lehmann, Liadan Ita Oćallaghan, Yoav Shoham
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
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
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
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
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...