Intro
Preface
Organization
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators (Invited Talk)
Contents
LP-Based Algorithms for Multistage Minimization Problems
1 Introduction
2 Rounding Scheme for Some Prize-Collecting Problems
2.1 Rounding Scheme
2.2 Prize-Collecting Steiner Tree
2.3 Prize-Collecting Metric Traveling Salesman
3 Min Cut, Vertex Cover and IP2 Linear Problems
References
A Faster FPTAS for Knapsack Problem with Cardinality Constraint
1 Introduction
1.1 Theoretical Motivations and Contributions

1.2 Technique Overview
2 Item Preprocessing
3 Algorithm for Large Items
3.1 An Abstract Algorithm Based on Convolution
3.2 Discretizing the Function Domain
3.3 Fast Convolution Algorithm
4 Continuous Relaxation for Small Items
4.1 Continuous Relaxation Design and Error Analysis
4.2 Computing ""0365S Efficiently
5 Putting the Pieces Together-Combining Small and Large Items
6 Conclusion
References
Distributed Algorithms for Matching in Hypergraphs
1 Introduction
2 Our Contribution and Results
3 Related Work
4 A 3-Round O(d2)-Approximation

5 A O(logn)-Rounds d-Approximation Algorithm
6 A 3-Round O(d3)-Approximation Using HEDCSs
6.1 Sampling and Constructing an HEDCS in the MPC Model
7 Computational Experiments
7.1 Experiments with Random Uniform Hypergraphs
7.2 Experiments with Real Data
7.3 Experimental Conclusions
8 Conclusion
References
Online Coloring and a New Type of Adversary for Online Graph Problems
1 Introduction
2 Preliminaries
2.1 Bins Vs. Colors
2.2 Saturated Bins
3 A New Type of Adversary
4 FirstFit on -colorable Graphs, Triangle-Free Graphs, and Trees

5 CBIP on Bipartite Graphs
6 Lower Bounds for Several Graph Classes
7 Conclusion and Open Problems
References
Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique
1 Introduction
2 Preliminaries
3 Maximum Coverage with Knapsack Constraints
4 Maximum Coverage with Cluster Constraints
5 Multiple Knapsack with Cluster Constraints
5.1 13-Approximation for MKPC with General Clusters
5.2 12-Approximation for MKPC with Isolation Property
References
A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon
1 Introduction

2 Structural Analysis
2.1 Visibility Polygons
2.2 Pockets
2.3 Holes
3 The Algorithm
4 Polygons Weakly Visible from a Chord
References
Lasserre Integrality Gaps for Graph Spanners and Related Problems
1 Introduction
1.1 Our Results and Techniques
2 Preliminaries: Lasserre Hierarchy
3 Projection Games: Background and Previous Work
4 Lasserre Integrality Gap for Directed (2k-1)-Spanner
4.1 Spanner LPs and Their Lasserre Lifts
4.2 Spanner Instance
4.3 Fractional Solution
4.4 Proof of Theorem 1
5 Undirected (2k-1)-Spanner
References