Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012, Proceedings Theoretical Computer Science and General Issues Series

A New Point of NP-Hardness for 2-to-1 Label Cover.-Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems .-Additive Approximation for Near-Perfect Phylogeny Construction.-Improved Spectral-Norm Bounds for Clustering.-Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs .-What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid.-Improved Hardness Results for Profit Maximization Pricing Problems

with Unlimited Supply.-Online Flow Time Scheduling in the Presence of Preemption Overhead.-Prize-Collecting Survivable Network Design in Node-Weighted Graphs .-Approximating Minimum-Cost Connected T -Joins .-iBGP and Constrained Connectivity.-Online Scheduling of Jobs with Fixed Start Times on Related Machines .-A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems .-Approximating Bounded Occurrence Ordering CSPs .-On the NP-Hardness of Max-Not-2 .-The Remote Set Problem on Lattices .-Approximation Algorithms for Generalized and Variable-Sized Bin Covering .-Approximating Minimum Linear Ordering Problems.-New Approximation Results for Resource Replication Problems .-Maximum Matching in Semi-streaming with Few Passes .-Improved Inapproximability for TSP .-Approximation Algorithm for Non-boolean MAX k-CSP .-Planarizing an Unknown Surface.-The Projection Games Conjecture and the NP-Hardness of In n-Approximating Set-Cover.-New and Improved Bounds for the Minimum Set Cover Problem.-Hardness of Vertex Deletion and Project Scheduling.-Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues .-Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four (Extended Abstract).-Spectral Norm of Symmetric Functions .-Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions.-Testing Permanent Oracles – Revisited.-Limitations of Local Filters of Lipschitz and Monotone Functions .-Testing Lipschitz Functions on Hypergrid Domains .-Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic.-Multiple-Choice Balanced Allocation in (Almost) Parallel.-Optimal Hitting Sets for Combinatorial Shapes.-Tight Bounds for Testing k-Linearity.-Pseudorandomness for Linear Length Branching Programs and Stack Machines.-A Discrepancy Lower Bound for Information Complexity.-On the Coin Weighing Problem with the Presence of Noise.-Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming.-An Explicit VC-Theorem for Low-Degree Polynomials .-Tight Bounds on the Threshold for Permuted k-Colorability.-Sparse and Lopsided Set Disjointness via Information Theory.-Maximal Empty Boxes Amidst Random Points .-Rainbow Connectivity of Sparse Random Graphs.-Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors .-Two-Sided Error Proximity Oblivious Testing (Extended Abstract).-Mirror Descent Based Database Privacy.-Analysis of k-Means++ for Separable Data.-A Sharper Local Lemma with Improved Applications.-Finding Small Sparse Cuts by Random Walk.-On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation.-A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller Codes.-A Combination of Testability and Decodability by Tensor Products Extractors for Turing-Machine Sources.