Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings

Front Matter....Pages -
New Tools for Graph Coloring....Pages 1-12
Inapproximability of NP-Complete Variants of Nash Equilibrium....Pages 13-25
Sparse Recovery with Partial Support Knowledge....Pages 26-37
On Capacitated Set Cover Problems....Pages 38-49
Bandwidth and Low Dimensional Embedding....Pages 50-61
 O (1)-Approximations for Maximum Movement Problems....Pages 62-74
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs....Pages 75-86
Social Welfare in One-Sided Matching Markets without Money....Pages 87-98
Primal-Dual Schema and Lagrangian Relaxation for the k -Location-Routing Problem....Pages 99-110
Scheduling Resources for Throughput Maximization....Pages 111-122
Coloring and Maximum Independent Set of Rectangles....Pages 123-134
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems....Pages 135-146
A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius....Pages 147-157
Periodicity and Cyclic Shifts via Linear Sketches....Pages 158-170
An Approximation Algorithm for the Tree t -Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs....Pages 171-183
Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle....Pages 184-193
Opaque Sets....Pages 194-205
Exploring and Triangulating a Region by a Swarm of Robots....Pages 206-217
Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)....Pages 218-229
Locating Depots for Capacitated Vehicle Routing....Pages 230-241
Satisfying Degree- d Equations over GF [2] n ....Pages 242-253
Black-Box Reductions in Mechanism Design....Pages 254-265
Multiplicative Approximations of Random Walk Transition Probabilities....Pages 266-276
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems....Pages 277-288
Network-Design with Degree Constraints....Pages 289-301
Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems....Pages 302-314
Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions....Pages 315-326
Nearly Optimal NP-Hardness of Vertex Cover on k -Uniform k -Partite Hypergraphs....Pages 327-338
A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs....Pages 339-350
Viral Processes by Random Walks on Random Regular Graphs....Pages 351-364
Quantum Property Testing for Bounded-Degree Graphs....Pages 365-376
Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification....Pages 377-388
Testing Graph Blow-Up....Pages 389-399
On Sums of Locally Testable Affine Invariant Properties....Pages 400-411
Limits on the Rate of Locally Testable Affine-Invariant Codes....Pages 412-423
The Computational Complexity of Estimating MCMC Convergence Time....Pages 424-435
Streaming Algorithms with One-Sided Estimation....Pages 436-447
Everywhere-Tight Information Cost Tradeoffs for Augmented Index....Pages 448-459
A Canonical Form for Testing Boolean Function Properties....Pages 460-471
Independent Sets in Random Graphs from the Weighted Second Moment Method....Pages 472-482
Extractors and Lower Bounds for Locally Samplable Sources....Pages 483-494
A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma....Pages 495-506
Dense Locally Testable Codes Cannot Have Constant Rate and Distance....Pages 507-518
Efficient Probabilistically Checkable Debates....Pages 519-529
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs....Pages 530-541
Inflatable Graph Properties and Natural Property Tests....Pages 542-554
Fast Simulation of Large-Scale Growth Models....Pages 555-566
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model....Pages 567-578
Proximity Oblivious Testing and the Role of Invariances....Pages 579-592
Optimal Rate List Decoding via Derivative Codes....Pages 593-604
Public Key Locally Decodable Codes with Short Keys....Pages 605-615
On Sampling from Multivariate Distributions....Pages 616-627
Almost Optimal Explicit Johnson-Lindenstrauss Families....Pages 628-639
Correlation Bounds for Poly-size $\\mbox{\\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates....Pages 640-651
Clustering in Interfering Binary Mixtures....Pages 652-663
Approximating the Influence of Monotone Boolean Functions in $O(\\sqrt{n})$ Query Complexity....Pages 664-675
On Approximating the Number of Relevant Variables in a Function....Pages 676-687
Query Complexity in Errorless Hardness Amplification....Pages 688-699
Back Matter....Pages -