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
Published on 5. August 2011
XV, 702 pages
978-3-642-22935-0 (ISBN)
Description
This book constitutes the joint refereed proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011, and the 15th International Workshop on Randomization and Computation, RANDOM 2011, held in Princeton, New Jersey, USA, in August 2011.
The volume presents 29 revised full papers of the APPROX 2011 workshop, selected from 66 submissions, and 29 revised full papers of the RANDOM 2011 workshop, selected from 64 submissions. They were carefully reviewed and selected for inclusion in the book. In addition two abstracts of invited talks are included.
APPROX focuses on algorithmic and complexity issues surrounding the development of efficient approximate solutions to computationally difficult problems. RANDOM is concerned with applications of randomness to computational and combinatorial problems.
More details
Other editions
Additional editions
Leslie Ann Goldberg | Klaus Jansen | R. Ravi
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
Book
08/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title page
- Preface
- Organization
- Table of Contents
- Contributed Talks of APPROX
- New Tools for Graph Coloring
- Introduction
- Our Results
- The SDP and Lasserre Hierarchy
- Understanding the SDP Solution
- Global Correlation, Local Correlation and Rounding
- Threshold Rank and Global Correlation
- Threshold Rank Bound for Distance Transitive Graphs
- Conclusion
- References
- Inapproximability of NP-Complete Variants of Nash Equilibrium
- Introduction
- A Sharp Result for Near-Optimal Approximate Nash
- The Bigger Picture: Hardness for NP-Hard Variants of Nash
- The Complexity of Approximate Pure Bayes Nash Equilibria
- Organization
- Preliminaries
- Approximate Equilibria with Good Value
- The Reduction
- Hardness for Close to 1/2
- Distinguishing between Low and High Value
- An Algorithm for Good 1/2-Approximate Equilibria
- Finding a Second Equilibrium
- Small Support Equilibria
- Computing Approximate Pure Bayes-Nash Equilibrium
- References
- Sparse Recovery with Partial Support Knowledge
- Introduction
- Preliminaries
- Lower Bounds
- Upper Bounds
- References
- On Capacitated Set Cover Problems
- Introduction
- Our Results
- Other Related Work
- Bounding the Integrality Gap of PSC's
- Set Systems with Small Hereditary Discrepancy
- Rounding Procedure
- Analysis
- Set Systems with Small VC Dimension
- Lower Bounds
- References
- Bandwidth and Low Dimensional Embedding
- Introduction
- Summary of Techniques
- Embedding in the Doubling Dimension
- Preliminaries and Definitions
- Low Dimensional Embedding
- Low Distortion p-Embeddings of Low Bandwidth Graphs
- Preliminaries and Definitions
- Proof of Theorem 3
- Tree Bandwidth
- References
- O(1)-Approximations for Maximum Movement Problems
- Introduction
- s-t Path Movement Problem
- Straighter Paths
- Connectivity Movement Problem
- A Constant Factor Approximation for Connectivity Movement Problem
- References
- Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
- Introduction
- Previous Work and Our Results
- Lower Bound Constructions
- Steiner Tree Problem
- Traveling Salesman Problem
- Strong Universal Lower Bounds Imply Privacy Lower Bounds
- References
- Social Welfare in One-Sided Matching Markets without Money
- Introduction
- Preliminaries
- Other Related Work
- Ordinal Welfare Factor of RSD and PS Mechanisms
- Ordinal Welfare Factor of RSD
- RSD and Online Bipartite Matching
- Ordinal Welfare Factor of PS
- Linear Welfare Factor of RSD and PS
- Concluding Remarks
- References
- Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem
- Introduction
- The k-Location-Routing Problem
- References
- Scheduling Resources for Throughput Maximization
- Introduction
- Outline of Our Algorithm
- Height-Bounded Star Solutions: Proof of Theorem 2
- Transformation to 2-Solutions
- Transformation to Height-Bounded Star Solutions
- Finding Height-Bounded Star Solutions
- LP Relaxation
- Rounding a Fractional Solution
- Overall Algorithm
- References
- Coloring and Maximum Independent Set of Rectangles
- Introduction
- Preliminaries
- Polynomially Bounded Weights
- Rectangle Coloring and Degenerate Instances
- Sparse Instances
- Independent Set and Coloring
- Coloring Algorithms
- O($q^2$)-Coloring
- An O($q^3/2$) Coloring for Restricted Setting
- Special Cases
- References
- A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
- Introduction
- A Pseudopolynomial Algorithm for $1||fj$
- A (2+)-Approximation Algorithm
- References
- A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius
- Introduction
- Proof of the Theorem
- Local Replacement Algorithm for Set-Cover
- Algorithm for Tree Augmentation
- Proof of Lemma
- A Tight Example for the Decomposition Lemma
- References
- Periodicity and Cyclic Shifts via Linear Sketches
- Introduction
- Our Results and Related Work
- Fourier Preliminaries and Choice of Distance Function
- Discrete Fourier Transform and Sketches
- Choice of Distance Function
- Periodicity
- Distance from Fixed Periodicity
- Determining Perfect Periodicity: Noiseless Case
- Determining Perfect Periodicity: Noisy Case
- Cyclic Shifts
- Cyclic Shift Distance
- Conclusion
- References
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Introduction
- Preliminaries
- Tree Spanners of Chordal Graphs
- Tree Spanners of Generalized Chordal Graphs
- Approximating Tree t-Spanners of General Graphs
- References
- Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle
- Introduction
- Preliminaries
- Notation
- Lattice Problems
- Some Basic Tools
- Reducing CVP to SVP
- Analysis of Runtime
- References
- Opaque Sets
- Introduction
- Preliminaries
- Connected Barriers
- Single-arc Barriers
- Arbitrary Barriers
- Interior-Restricted Versus Unrestricted Barriers
- Concluding Remarks
- References
- Exploring and Triangulating a Region by a Swarm of Robots
- Introduction
- Notation and Preliminaries
- NP-Hardness
- Online Minimum Relay Triangulation
- Offline Minimum Relay Triangulation
- Online Maximum Area Triangulation
- Conclusions
- References
- Improved Competitive Ratios for Submodular Secretary Problems
- Introduction
- Our Results
- Related Work
- Preliminaries
- (1- ln 2)/2 ~ 0.153-Competitive Algorithm for SPMS
- Analysis of a Single Gi
- Analysis of the Entire Output
- The Submodular Cardinality Secretary Problem
- The Submodular Knapsack Secretary Problem
- References
- Locating Depots for Capacitated Vehicle Routing
- Introduction
- Reducing k-LocVRP to k Median Forest
- Multi-swap Local Search for Median Forest
- References
- Satisfying Degree-d Equations over GF$[2]^n$
- Introduction
- Preliminaries
- The Case of Non-perfect Completeness
- Completely Satisfiable Systems
- Consequences for Max-CSPs
- Final Words
- References
- Black-Box Reductions in Mechanism Design
- Introduction
- Preliminaries
- Symmetric Single-Parameter Mechanism Design
- Construction of the Range
- General SPMD: Limitation of MIR Mechanisms
- Symmetric Multi-Parameter Mechanism Design
- References
- Multiplicative Approximations of Random Walk Transition Probabilities
- Introduction
- Related Work
- Our Results and Techniques
- Directed Graphs
- References
- Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
- Introduction
- Notation
- Intuition and Algorithm
- Analysisof $s^1$
- Analysisof $s^2$
- Analysisof $p^3$
- References
- Network-Design with Degree Constraints
- Introduction
- Problems Considered
- Previous and Related Work
- Our Results
- Algorithm for Degree-Constrained 2-Connected Subgraph
- Algorithm for Minimum Degree k-Arborescence
- References
- Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems
- Introduction
- Preliminaries
- A 3-Approximation Algorithm for MMkTC
- A 2.5 -Approximation Algorithm for BTC
- References
- Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions
- Introduction
- Generalizations of Sparsest Cut
- Our Results
- Monotonicity of Eigenvalues
- Sparsest m-Partition
- Finding Sparsest Small Sets
- References
- Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
- Introduction
- Cross-Intersecting Set Families
- Multi-Layered PCP
- Hardness Reduction for HypVC-Partite
- Construction of the Hypergraph
- Completeness
- Soundness
- References
- A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs
- Introduction
- Preliminaries
- Tree Models
- Tree Models of Constant Size
- Constant Size Nets for Constant Size Models
- Proof of the Main Result
- PARTITION(M0,f0)
- Constructing a Tree from a Close Partition
- References
- Contributed Talks of RANDOM
- Viral Processes by Random Walks on Random Regular Graphs
- Introduction
- Model
- Results
- Related Work
- Assumptions and Approach
- Two-Particle System
- Interaction Graph Framework: SI Model
- Interaction Graph Approximation
- Completion Time
- Interaction Graph Framework: SIR Model
- References
- Quantum Property Testing for Bounded-Degree Graphs
- Introduction
- Quantum Algorithms for Bipartiteness and Expansion
- Quantum Lower Bound for Testing Expansion
- Overview
- Proof of Lemma 1
- References
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Introduction
- Background on Hardness Amplification
- Non-uniform Reductions for Hardness Amplification
- Our Results
- Related Work
- Technique
- Conclusion and Open Problem
- References
- Testing Graph Blow-Up
- Introduction
- Preliminaries
- Basic Notions
- The Blow-Up Properties
- The BU(H)-Tester and Its Basic Features
- The Acceptance Condition and Graphs That Are Far from BU(H)
- Basic Notions and Notations
- The Progress Lemma
- Proximity Oblivious Testing of Blow-Up
- Conclusions
- References
- On Sums of Locally Testable Affine Invariant Properties
- Introduction
- Main Result
- The Structure of Affine-Invariant Properties
- Sums of Affine-Invariant Properties
- Proof of Main Theorem
- Consequences, Questions and Conjectures
- Known Locally Testable Properties
- Conjectures and Questions
- References
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- Introduction
- Locally Correctable and Locally Testable Codes, Affine-Invariance, and Main Result
- Algebraic Property Testing
- Definitions and Main Results
- Preliminaries - Locally Testable, and Reed-Muller Codes
- Affine Invariant Codes
- Proof of Main Theorems
- Uniform Homogenous Diagonal Systems of Polynomial Equations
- Proof of Main Theorem
- Proof of Theorem 3
- References
- The Computational Complexity of Estimating MCMC Convergence Time
- Introduction
- Preliminaries and Results
- Given Starting Point
- Arbitrary Starting Point
- Arbitrary Mixing Times
- Protocols for Statistical Distance
- An AM protocol
- A coAM protocol
- Diagnosing Convergence for Polynomially Mixing Chains
- Discussion and Future Directions
- References
- Streaming Algorithms with One-Sided Estimation
- Introduction
- Our Problems
- Preliminaries
- Space Complexity Separations
- Upper Bounds
- Lower Bounds
- References
- Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- Introduction
- Preliminaries, Context, and Our Result
- Formal Version of Main Theorem and Proof Outline
- Proofs of Technical Lemmas
- Derivation of (4)
- Derivation of (5)
- Derivation of (6)
- References
- Canonical Form for Testing Boolean Function Properties
- Introduction
- Preliminaries
- The Testing Algorithms We Can Canonicalize: Independent Testers
- A Canonical Form for Testers, and Our Main Results
- Main Results
- Overview of the Proofs of Theorems 3 and 4
- Two-Sided Independent Testers and Classes Closed under Noisy-Neg Minors
- One-Sided Independent Testers and Classes Closed under ID-Neg Minors
- References
- Independent Sets in Random Graphs from the Weighted Second Moment Method
- Introduction
- The Weighted Second Moment Method
- Finding and Bounding the Maxima
- Proofs
- References
- Extractors and Lower Bounds for Locally Samplable Sources
- Introduction
- Results
- Techniques
- Preliminaries
- 1-Local Sources
- d-Local Sources
- Superindependent Matchings
- Proof of Theorem 6
- Increasing the Output Length
- Improved Lower Bounds for Sampling Input-Output Pairs
- References
- A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
- Introduction
- Background and Motivation
- The Main Result
- Paper Overview
- A Spectral Condition for FK-Regularity
- Finding the First Eigenvalue Deterministically
- Concluding Remarks and Open Problems
- References
- Dense Locally Testable Codes Cannot Have Constant Rate and Distance
- Introduction
- Our Results
- Moderately Dense 3-query LTCs Cannot Be c3
- Proof of Lemma 2
- Proof of Lemma 3
- Exploring Possible Improvements
- Tradeoff between Rate and Density
- For q&3 Density Must Be High
- Allowing Weighted Hypergraph-Tests
- References
- Efficient Probabilistically Checkable Debates
- Introduction
- Debate Systems
- Probabilistically Checkable Debates
- The Inapproximability Connection
- Our Result
- Our Techniques
- Questions for Future Work
- References
- An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
- Introduction
- Overview of Our Techniques
- Definitions
- Local Isolated Neighborhoods in Constant Treewidth Graphs
- Isolated Neighborhoods
- Finding an Isolated Neighborhood of a Vertex
- Finding Isolated Neighborhoods Covering a Vertex
- Small Cover of Isolated Neighborhoods
- The Partitioning Oracle (Proof of Theorem 1)
- References
- Inflatable Graph Properties and Natural Property Tests
- Introduction
- Preliminaries
- Graph Properties and the Dense Model for Property Testing
- Features of Property Tests
- Features of Graph Properties
- Fixed-Order Subgraph Distributions of Graphs
- Our Results
- Naturalizing Tests - Proof of Theorem 1
- Open Questions
- References
- Fast Simulation of Large-Scale Growth Models
- Introduction
- Formal Model
- Least Action Principle
- Algorithm: From Approximation to Exact Calculation
- Experimental Results
- Rotor-Router Aggregation
- Internal Diffusion Limited Aggregation (IDLA)
- References
- Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
- Introduction
- Technical Overview
- Phase Transition Revisited
- First Moment of the Partition Function
- Second Moment of the Partition Function
- On the Use of Computational Assistance
- Analysis of the Second Moment Function
- References
- Proximity Oblivious Testing and the Role of Invariances
- Introduction
- General Framework
- Characterization by Generated Constraints
- The Invariance Condition
- Models of Property Testing
- The Invariance Conjecture Holds in the Dense Graph Model
- The Invariance Conjecture in the Bounded-Degree Graph Model
- The Invariance Conjecture Fails in Some Cases
- The Invariance Condition Is Not Necessary for POT
- The Invariance Condition Is Not Sufficient for POT
- Conclusions
- References
- Optimal Rate List Decoding via Derivative Codes
- Introduction
- Background
- This Work
- Derivative Codes
- List Decoding Derivative Codes
- Interpolation
- Retrieving Candidate Polynomials
- Some Remarks
- Reducing the List Size
- Decoding with Side Information
- References
- Public Key Locally Decodable Codes with Short Keys
- Introduction
- Previous Work
- Our Contributions
- Notation
- Locally Decodable Codes
- Construction
- Conclusion
- References
- On Sampling from Multivariate Distributions
- Introduction
- Warm-Up: Discrete Case
- Continuous Case
- Correlated Distributions
- Product Distributions
- Conclusions and Open Problems
- References
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- Introduction
- Derandomizing JLL
- Optimality of JLL
- Related Work
- Outline of Constructions
- Preliminaries
- Strong JL Distributions
- A Generic JL Derandomization Template
- Explicit JL Families via Samplers
- Optimality of JL Lemma
- References
- Correlation Bounds for Poly-size $AC^0$ Circuits with $n^1-o(1)$ Symmetric Gates
- Introduction
- Preliminaries
- An Illustrative Example: Correlation Bounds for Sparse Polynomials
- Correlation Bounds for AC0 with a Few Symmetric and Threshold Gates
- Useful Lemmas
- Correlation Bounds for Polynomial-size Circuits
- References
- Clustering in Interfering Binary Mixtures
- Introduction
- Binary Mixtures and the Clustering Property
- Interfering Binary Mixtures
- The Clustering Property
- Main Results
- HighDensityof B-tiles
- LowDensityof B-tiles
- OtherModels
- Interfering Binary Mixtures
- Noninterfering Binary Mixtures
- References
- Approximating the Influence of Monotone Boolean Functions in O(Vn) Query Complexity
- Introduction
- Preliminaries
- The Algorithm
- A Lower Bound
- References
- On Approximating the Number of Relevant Variables in a Function
- Introduction
- Preliminaries
- Distinguishing between k-Juntas and Functions Far from Every (1 + ?)k-Junta
- The Lower Bound
- The Algorithm
- Restricting the Problem to Classes of Functions
- Linear Functions
- Polynomials over GF(2)
- References
- Query Complexity in Errorless Hardness Amplification
- Introduction
- The Errorless XOR Lemma
- Monotone Errorless Amplification
- Preliminaries
- Proof of Theorem 1
- Proof of Theorem 2
- References
- Author Index
