Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Name: 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
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011, Proceedings

Leslie Ann Goldberg Klaus Jansen R. Ravi José D.P. Rolim(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 5. August 2011

XV, 702 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22935-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken