𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the approximability of Dodgson and Young elections

✍ Scribed by Ioannis Caragiannis; Jason A. Covey; Michal Feldman; Christopher M. Homan; Christos Kaklamanis; Nikos Karanikolas; Ariel D. Procaccia; Jeffrey S. Rosenschein

Book ID
113469363
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
315 KB
Volume
187-188
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the approximability of clique and rel
On the approximability of clique and related maximization problems
✍ Aravind Srinivasan πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 247 KB

We consider approximations of the form n 1Γ€oΓ°1Þ for the Maximum Clique problem, where n is the number of vertices in the input graph and where the ''oΓ°1Þ'' term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability re

On the approximability of the Steiner tr
On the approximability of the Steiner tree problem
✍ Martin Thimm πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 165 KB

We show that it is not possible to approximate the minimum Steiner tree problem within 1 + 1 162 unless RP = NP. The currently best known lower bound is 1 + 1 400 . The reduction is from H astad's nonapproximability result for maximum satisΓΏability of linear equation modulo 2. The improvement on the