Skip to main content
SpringerLink
Log in

Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Ashish Goel
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. José D. P. Rolim
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Ronitt Rubinfeld
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5171)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (47 papers)

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. Approximating Optimal Binary Decision Trees

      • Micah Adler, Brent Heeringa
      Pages 1-9

    2. Santa Claus Meets Hypergraph Matchings

      • Arash Asadpour, Uriel Feige, Amin Saberi
      Pages 10-20

    3. Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction

      • Mihai Bădoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, Morteza Zadimoghaddam
      Pages 21-34

    4. Connected Vertex Covers in Dense Graphs

      • Jean Cardinal, Eythan Levy
      Pages 35-48

    5. Improved Approximation Guarantees through Higher Levels of SDP Hierarchies

      • Eden Chlamtac, Gyanit Singh
      Pages 49-62

    6. Sweeping Points

      • Adrian Dumitrescu, Minghui Jiang
      Pages 63-76

    7. Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness

      • Venkatesan Guruswami, Prasad Raghavendra
      Pages 77-90

    8. Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks

      • Nir Halman, Chung-Lun Li, David Simchi-Levi
      Pages 91-103

    9. Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP

      • David R. Karger, Jacob Scott
      Pages 104-117

    10. Approximating Maximum Subgraphs without Short Cycles

      • Guy Kortsarz, Michael Langberg, Zeev Nutov
      Pages 118-131

    11. Deterministic 7/8-Approximation for the Metric Maximum TSP

      • Łukasz Kowalik, Marcin Mucha
      Pages 132-145

    12. Inapproximability of Survivable Networks

      • Yuval Lando, Zeev Nutov
      Pages 146-152

    13. Approximating Single Machine Scheduling with Scenarios

      • Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson
      Pages 153-164

    14. Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity

      • Richard Matthew McCutchen, Samir Khuller
      Pages 165-178

    15. A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One

      • Shashi Mittal, Andreas S. Schulz
      Pages 179-192

    16. The Directed Minimum Latency Problem

      • Viswanath Nagarajan, R. Ravi
      Pages 193-206

    17. A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem

      • Thành Nguyen
      Pages 207-218

    18. Approximating Directed Weighted-Degree Constrained Networks

      • Zeev Nutov
      Pages 219-232

    19. A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs

      • MohammadAli Safari, Mohammad R. Salavatipour
      Pages 233-246
Back to top

Other volumes

  1. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Keywords

About this book

This volume contains the papers presented at the 11th International Wo- shop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008) and the 12th International Workshop on Randomization and Computation (RANDOM 2008), which took place concurrently at the MIT (M- sachusetts Institute of Technology) in Boston, USA, during August 25–27, 2008. APPROX focuses on algorithmic and complexity issues surrounding the development of e?cient approximate solutions to computationally di?cult problems, and was the 11th in the series after Aalborg (1998), Berkeley (1999), Saarbru ¨cken (2000), Berkeley (2001), Rome (2002), Princeton (2003), Cambridge (2004), Berkeley (2005), Barcelona (2006), and Princeton (2007). RANDOM is concerned with applications of randomness to computational and combinatorial problems, and was the 12th workshop in the series following Bologna (1997), Barcelona (1998), Berkeley (1999), Geneva (2000), Berkeley (2001), Harvard (2002), Princeton (2003), Cambridge (2004), Berkeley (2005), Barcelona (2006), and Princeton (2007). Topics of interest for APPROX and RANDOM are: design and analysis of - proximation algorithms, hardness of approximation, small space, sub-linear time, streaming, algorithms, embeddings and metric space methods, mathematical programming methods, combinatorial problems in graphs and networks, game t- ory, markets, economic applications, geometric problems, packing, covering, scheduling, approximate learning, design and analysis of randomized algorithms, randomized complexity theory, pseudorandomness and derandomization, random combinatorial structures, random walks/Markov chains, expander graphs and randomness extractors, probabilistic proof systems, random projections and - beddings, error-correcting codes,average-case analysis, property testing, com- tational learning theory, and other applications of approximation and randomness.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation