List of accepted papers for APPROX 2009:


Ashkan Aazami, Joseph Cheriyan and Krishnam Raju Jampani. 
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs

Julia Chuzhoy and Paolo Codenotti. 
Resource Minimization Job Scheduling

Ronald Koch, Britta Peis, Martin Skutella and Andreas Wiese. 
Real-Time Message Routing and Scheduling

Katarzyna Paluch, Marcin Mucha and Aleksander Madry. 
A 7/9 Approximation Algorithm for the Maximum Traveling Salesman Problem

Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev and Maxim Sviridenko. 
On Hardness of Pricing Items for Single-Minded Bidders

Friedrich Eisenbrand and Thomas Rothvoss. 
New Hardness Results for Diophantine Approximation

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar and Danny Segev. 
Scheduling with Outliers

Saurav Pandit, Sriram Pemmaraju and Kasturi Varadarajan. 
Approximation Algorithms for Domatic Partitions

Brian Tagiku, Adam Meyerson and Douglas Carroll. 
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs

Avner Magen and Mohammad Moharrami. 
Robust algorithms for Maximum Independent Set on Minor-free graphs based on the Sherali-Adams Hierarchy

Jon Lee, Maxim Sviridenko and Jan Vondrak. 
Submodular Maximization Over Multiple Matroids via Generalized Exchange Properties

Chandra Chekuri and Iftah Gamzu. 
Truthful Mechanisms via Greedy Iterative Packing

Gaurav Kanade, Matt Gibson, Kasturi Varadarajan and Erik Krohn. 
An Approximation Scheme for Terrain Guarding

Venkatesan Guruswami and Ali Kemal Sinop. 
Improved Inapproximability Results for Maximum k-Colorable Subgraph

Chandra Chekuri, Alina Ene and Nitish Korula. 
Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

Alexander Jaffe, James Lee and Mohammad Moharrami. 
On the optimality of gluing over scales

Rolf Harren and Rob van Stee. 
Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

Thomas Rothvoss and Laura Sanita. 
On the complexity of the asymmetric VPN problem

Jose R. Correa, Martin Skutella and Jose Verschae. 
The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders

Brian Tagiku and Adam Meyerson. 
Minimizing Average Shortest Path Distances via Shortcut Edge Addition

Zeev Nutov. 
Approximating Node-Connectivity Augmentation Problems

Guy Kortsraz and Zeev Nutov. 
Approximating some network design problems with node costs

Konstantinos Georgiou, Avner Magen and Madhur Tulsiani. 
Optimal Sherali-Adams Gaps from Pairwise Independence

Uriel Feige, Nicole Immorlica, Vahab Mirrokni and Hamid Nazerzadeh. 
Pass Approximation: A Framework for Analyzing and Designing Heuristics

Ankit Aggarwal, Amit Deshpande and Ravi Kannan. 
Adaptive Sampling for k-means Clustering