Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings

Front Matter....Pages -
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem....Pages 1-11
Improved Inapproximability for Submodular Maximization....Pages 12-24
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems....Pages 25-38
Submodular Secretary Problem and Extensions....Pages 39-52
Approximation Algorithms for Min-Max Generalization Problems....Pages 53-66
Min-Power Strong Connectivity....Pages 67-80
The Complexity of Approximately Counting Stable Matchings....Pages 81-94
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs....Pages 95-109
Approximating Linear Threshold Predicates....Pages 110-123
Approximating Sparsest Cut in Graphs of Bounded Treewidth....Pages 124-137
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors....Pages 138-151
Vertex Sparsifiers: New Results from Old Techniques....Pages 152-165
PTAS for Weighted Set Cover on Unit Squares....Pages 166-177
Improved Lower Bounds for the Universal and a priori TSP....Pages 178-191
Proximity Algorithms for Nearly-Doubling Spaces....Pages 192-204
Matrix Sparsification and the Sparse Null Space Problem....Pages 205-218
The Checkpoint Problem....Pages 219-231
The Euclidean Distortion of Flat Tori....Pages 232-245
Online Embeddings....Pages 246-259
Approximation Algorithms for Intersection Graphs....Pages 260-273
An O (log n )-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs....Pages 274-286
Improved Algorithm for the Half-Disjoint Paths Problem....Pages 287-297
Approximate Lasserre Integrality Gap for Unique Games....Pages 298-311
Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses....Pages 312-325
Maximum Flows on Disjoint Paths....Pages 326-337
Approximation Algorithms for Reliable Stochastic Combinatorial Optimization....Pages 338-351
How to Schedule When You Have to Buy Your Energy....Pages 352-365
Improving Integrality Gaps via Chvátal-Gomory Rounding....Pages 366-379
Uniform Derandomization from Pathetic Lower Bounds....Pages 380-393
Testing Boolean Function Isomorphism....Pages 394-405
Better Size Estimation for Sparse Matrix Products....Pages 406-419
Low Rate Is Insufficient for Local Testability....Pages 420-433
Reconstruction Threshold for the Hardcore Model....Pages 434-447
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners....Pages 448-461
Monotonicity Testing and Shortest-Path Routing on the Cube....Pages 462-475
Better Gap-Hamming Lower Bounds via Better Round Elimination....Pages 476-489
Propagation Connectivity of Random Hypergraphs....Pages 490-503
Improved Pseudorandom Generators for Depth 2 Circuits....Pages 504-517
The Structure of Winning Strategies in Parallel Repetition Games....Pages 518-530
Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries....Pages 531-544
Periodicity in Streams....Pages 545-559
Rumor Spreading on Random Regular Graphs and Expanders....Pages 560-573
On Testing Computability by Small Width OBDDs....Pages 574-587
Learning and Lower Bounds for AC 0 with Threshold Gates....Pages 588-601
Liftings of Tree-Structured Markov Chains....Pages 602-616
Constructive Proofs of Concentration Bounds....Pages 617-631
Almost-Euclidean Subspaces of $\\ell_1^N$ via Tensor Products: A Simple Approach to Randomness Reduction....Pages 632-641
Testing Outerplanarity of Bounded Degree Graphs....Pages 642-655
Two-Source Extractors Secure against Quantum Adversaries....Pages 656-669
Locally Testable vs. Locally Decodable Codes....Pages 670-682
Differential Privacy and the Fat-Shattering Dimension of Linear Queries....Pages 683-695
Two Theorems on List Decoding....Pages 696-709
Delaying Satisfiability for Random 2SAT....Pages 710-723
Improved Rounding for Parallel Repeated Unique Games....Pages 724-737
A Query Efficient Non-adaptive Long Code Test with Perfect Completeness....Pages 738-751
Relativized Worlds without Worst-Case to Average-Case Reductions for NP....Pages 752-765
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field....Pages 766-779
Back Matter....Pages -