Approximation algorithms for NP-hard problems

DOI10.4171/OWR/2004/28MaRDI QIDQ555978zbMATH OpenOpenAlexFDO

Authors

Publication date 10 June 2005

Published in Oberwolfach Reports (Search for Journal in Brave)

Full work available at URL http://www.ems-ph.org/journals/show_issue.php?issn=1660-8933&vol=1&iss=3

Collections of abstracts of lectures (00B05) Approximation algorithms (68W25) Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming (90-06) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Contributions: -- Alexander Barvinok (joint with Alex Samorodnitsky), Fast and Crude Combinatorial Counting p.1463 -- Markus Bläser, A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One p.1465 -- Janka Chlebíková, Approximation Hardness of Optimization Problems p.1467 -- Amin Coja-Oghlan, Coloring Semirandom Graphs Optimally p.1470 -- Mary Cryan (joint with Martin Dyer, Haiko Müller and Leed Stougie), The Natural Random Walk on the Transportation Polytope when the Number of Sources is Constant p.1472 -- Artur Czumaj (joint with Christian Sohler and in part with Mihai Bădoiu, Piotr Indyk, and Anastasios Sidiropoulos), Sublinear Time Approximations for Metric MST and Facility Location Problems p.1474 -- Petros Drineas, Pass-Efficient Algorithms for Approximating Large Matrices p.1476 -- Martin Dyer, Counting knapsack solutions p.1480 -- Lars Engebretsen, More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP p.1482 -- Uriel Feige (joint with Shimon Kogan), The Hardness of Approximating Hereditary Properties p.1485 -- Sudipto Guha, An \(\Omega(\log^*n)\) Hardness of Approximation for the Asymmetric \(k\)-Center Problem p.1487 -- Johan Håstad (joint with S.Venkatesh), On the advantage over a random assignment p.1490 -- Mathias Hauptmann, PTAS for Dense Steiner Tree Problems p.1492 -- Tom Hayes (joint with Eric Vigoda), Coupling with Stationarity: Rapid Sampling for Graph Coloring p.1495 -- Dorit Hochbaum, Transformations to totally unimodular optimizations, Half Integrality and 2-Approximations p.1496 -- Stefan Hougardy (joint with Doratha E.Drake), Approximation Algorithms for the Weighted Matching Problem p.1499 -- Klaus Jansen, Improved approximation algorithm for the mixed fractional packing and covering problem p.1502 -- Ravi Kannan (joint with Noga Alon, W.Fernandez de la Vega, and Marek Karpinski), Random Sampling and Approximation of MAX-CSP Problems p.1505 -- Marek Karpinski (joint with Piotr Berman and Alex D.Scott), Approximation Hardness of Short Symmetric Instances of MAX-3SAT p.1507 -- Michael Langberg (joint with Adi Avidor), On Multicuts and Related Problems p.1509 -- Monique Laurent (joint with Etienne de Klerk and Pablo Parrilo), A PTAS for the minimization of polynomials of fixed degree over the simplex p.1513 -- R.Ravi (joint with Anupam Gupta and Amitabh Sinha), Boosted Sampling: Approximation Algorithms for Stochastic Optimization p.1516 -- R.Reischuk (joint with Jan Arpe), Robust Inference of Relevant Attributes p.1519 -- Angelika Steger (joint with Jan Remy and Alexander Souza), Average Case Analysis: Two Seemingly Simple Problems p.1520 -- Berthold Vöcking (joint with Rene Beier), Typical Properties of Winners and Losers in Discrete Optimization p.1523 -- Lars Engebretsen, Uriel Feige and Johan Håstad, On three recent results by Subhash Khot p.1525 -- Mathias Hauptmann, Special Session on Steiner Tree Problems p.1526 -- Nicolas Schabanel, Special Session on Near Optimal Decentralized Routing in Long Range Contact Networks p.1527 -- Berthold Vöcking (joint with Piotr Krysta), Special Session on Approximating Combinatorial Auctions without Randomized Routing p.1528 -- Open Problem Session p.1531

Recommendations

Cited in

(7)

This page was built for publication: Approximation algorithms for NP-hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q555978)