You have Guest access.
Log In
Chandra Chekuri, Klaus Jansen, José D.P. Rolim and Luca Trevisan
Front matter
609
The Network as a Storage Device: Dynamic Routing with Bounded Buffers
608
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT
611
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs
A Rounding Algorithm for Approximating Minimum Manhattan Networks (Extended Abstract)
Packing Element-Disjoint Steiner Trees
Approximating the Bandwidth of Caterpillars
Where’s the Winner? Max-Finding and Sorting with Metric Costs
606
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
The Complexity of Making Unique Choices: Approximating 1-in-k SAT
Approximating the Distortion
605
Approximating the Best-Fit Tree Under Lp Norms
607
Beating a Random Assignment
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints
Approximation Algorithms for Network Design and Facility Location with Service Capacities
611-612
Finding Graph Matchings in Data Streams
610
A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses
Efficient Approximation of Convex Recolorings
Approximation Algorithms for Requirement Cut on Graphs
642
Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems
Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy
Bounds for Error Reduction with Few Quantum Queries
Sampling Bounds for Stochastic Optimization
An Improved Analysis of Mergers
612
Finding a Maximum Independent Set in a Sparse Random Graph
On the Error Parameter of Dispersers
Tolerant Locally Testable Codes
A Lower Bound on List Size for List Decoding
A Lower Bound for Distribution-Free Monotonicity Testing
On Learning Random DNF Formulas Under the Uniform Distribution
Derandomized Constructions of k-Wise (Almost) Independent Permutations
Testing Periodicity
The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem (Extended Abstract)
The Online Clique Avoidance Game on Random Graphs
A Generating Function Method for the Average-Case Analysis of DPLL
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas
Mixing Points on a Circle
Derandomized Squaring of Graphs
Tight Bounds for String Reconstruction Using Substring Queries
Reconstructive Dispersers and Hitting Set Generators
The Tensor Product of Two Codes Is Not Necessarily Robustly Testable
610-611
Fractional Decompositions of Dense Hypergraphs
Back matter
This page requires script.
Frequently asked questions General info on journals and books Send us your feedback Impressum Contact us
© Springer, Part of Springer Science+Business Media Privacy, Disclaimer, Terms & Conditions, and Copyright Info