Ebook: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings

This book constitutes the proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013, and the 17th International Workshop on Randomization and Computation, RANDOM 2013, held in August 2013 in the USA. The total of 48 carefully reviewed and selected papers presented in this volume consist of 23 APPROX papers selected out of 46 submissions, and 25 RANDOM papers selected out of 52 submissions. APPROX 2013 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM 2013 focuses on applications of randomness to computational and combinatorial problems.

---

This book constitutes the proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013, and the 17th International Workshop on Randomization and Computation, RANDOM 2013, held in August 2013 in the USA. The total of 48 carefully reviewed and selected papers presented in this volume consist of 23 APPROX papers selected out of 46 submissions, and 25 RANDOM papers selected out of 52 submissions. APPROX 2013 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM 2013 focuses on applications of randomness to computational and combinatorial problems.

---

This book constitutes the proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013, and the 17th International Workshop on Randomization and Computation, RANDOM 2013, held in August 2013 in the USA. The total of 48 carefully reviewed and selected papers presented in this volume consist of 23 APPROX papers selected out of 46 submissions, and 25 RANDOM papers selected out of 52 submissions. APPROX 2013 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM 2013 focuses on applications of randomness to computational and combinatorial problems.
Content:
Front Matter....Pages -
Spectral Sparsification in Dynamic Graph Streams....Pages 1-10
The Online Stochastic Generalized Assignment Problem....Pages 11-25
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems....Pages 26-41
Approximating Large Frequency Moments with Pick-and-Drop Sampling....Pages 42-57
Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams....Pages 58-70
Capacitated Network Design on Undirected Graphs....Pages 71-80
Scheduling Subset Tests: One-Time, Continuous, and How They Relate....Pages 81-95
On the Total Perimeter of Homothetic Convex Bodies in a Convex Container....Pages 96-109
Partial Interval Set Cover – Trade-Offs between Scalability and Optimality....Pages 110-125
Online Square-into-Square Packing....Pages 126-141
Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions....Pages 142-157
Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems....Pages 158-172
Multiple Traveling Salesmen in Asymmetric Metrics....Pages 173-188
Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback....Pages 189-204
The Approximability of the Binary Paintshop Problem....Pages 205-217
Approximation Algorithms for Movement Repairmen....Pages 218-232
Improved Hardness of Approximating Chromatic Number....Pages 233-243
A Pseudo-approximation for the Genus of Hamiltonian Graphs....Pages 244-259
A Local Computation Approximation Scheme to Maximum Matching....Pages 260-273
Sketching Earth-Mover Distance on Graph Metrics....Pages 274-286
Online Multidimensional Load Balancing....Pages 287-302
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs....Pages 303-316
Interdiction Problems on Planar Graphs....Pages 317-331
Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration....Pages 332-346
Finding Heavy Hitters from Lossy or Noisy Data....Pages 347-362
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy....Pages 363-378
Fast Private Data Release Algorithms for Sparse Queries....Pages 379-394
Local Reconstructors and Tolerant Testers for Connectivity and Diameter....Pages 395-410
An Optimal Lower Bound for Monotonicity Testing over Hypergrids....Pages 411-424
Small-Bias Sets for Nonabelian Groups....Pages 425-435
What You Can Do with Coordinated Samples....Pages 436-451
Robust Randomness Amplifiers: Upper and Lower Bounds....Pages 452-467
The Power of Choice for Random Satisfiability....Pages 468-483
Connectivity of Random High Dimensional Geometric Graphs....Pages 484-496
Matching-Vector Families and LDCs over Large Modulo....Pages 497-512
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing....Pages 513-526
Testing Membership in Counter Automaton Languages....Pages 527-542
Tight Lower Bounds for Testing Linear Isomorphism....Pages 543-558
Randomness-Efficient Curve Samplers....Pages 559-574
Combinatorial Limitations of Average-Radius List Decoding....Pages 575-590
Zero Knowledge LTCs and Their Applications....Pages 591-606
A Tight Lower Bound for High Frequency Moment Estimation with Small Error....Pages 607-622
Improved FPTAS for Multi-spin Systems....Pages 623-638
Pseudorandomness for Regular Branching Programs via Fourier Analysis....Pages 639-654
Absolutely Sound Testing of Lifted Codes....Pages 655-670
On the Average Sensitivity and Density of k-CNF Formulas....Pages 671-682
Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions....Pages 683-698
Back Matter....Pages 699-713
....Pages -