Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Spectral Sparsification in Dynamic Graph Streams.- The Online Stochastic Generalized Assignment Problem.- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems.- Approximating Large Frequency Moments with Pick-and-Drop Sampling.- Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams.- Capacitated Network Design on Undirected Graphs.- Scheduling Subset Tests: One-Time, Continuous, and How They Relate.- On the Total Perimeter of Homothetic Convex Bodies in a Convex Container.- Partial Interval Set Cover - Trade-Offs between Scalability and Optimality.- Online Square-into-Square Packing.- Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions.- Shrinking Maxima, Decreasing Costs: New Online Packing andCovering Problems.- Multiple Traveling Salesmen in Asymmetric Metrics.- Approximate Indexability and Bandit Problems with Concave Rewardsand Delayed Feedback.- The Approximability of the Binary Paintshop Problem.- Approximation Algorithms for Movement Repairmen.- Improved Hardness of Approximating Chromatic Number.- A Pseudo-approximation for the Genus of Hamiltonian Graphs.- A Local Computation Approximation Scheme to Maximum Matching.- Sketching Earth-Mover Distance on Graph Metrics.- Online Multidimensional Load Balancing.- A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.- Interdiction Problems on Planar Graphs.- Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration.- Finding Heavy Hitters from Lossy or Noisy Data.- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy.- Phase Coexistence and Slow Mixing for the Hard-Core Model on Z2.- Fast Private Data Release Algorithms for Sparse Queries.- Local Reconstructors and Tolerant Testers for Connectivity and Diameter.- An Optimal Lower Bound for Monotonicity Testing over Hypergrids.- Small-Bias Sets for NonabelianGroups: