You have Guest access.
Log In
Josep Díaz, Klaus Jansen, José D.P. Rolim and Uri Zwick
Front matter
1
On Nontrivial Approximation of CSPs
2
Analysis of Algorithms on the Cores of Random Graphs
3-14
Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
15-26
Approximating Precedence-Constrained Single Machine Scheduling by Coloring
27-38
Minimizing Setup and Beam-On Times in Radiation Therapy
39-48
On the Value of Preemption in Scheduling
49-60
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs
61-69
Tight Results on Minimum Entropy Set Cover
70-81
A Tight Lower Bound for the Steiner Point Removal Problem on Trees
82-94
Single-Source Stochastic Routing
95-103
An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
104-115
Online Algorithms to Minimize Resource Reallocations and Network Communication
116-127
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
128-139
Combinatorial Algorithms for Data Migration to Minimize Average Completion Time
140-151
LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times
152-163
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
164-175
Improved Algorithms for Data Migration
176-187
Approximation Algorithms for Graph Homomorphism Problems
188-199
Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem
200-211
Hardness of Preemptive Finite Capacity Dial-a-Ride
212-223
Minimum Vehicle Routing with a Common Deadline
224-235
Stochastic Combinatorial Optimization with Controllable Risk Aversion Level
236-247
Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
248-259
Better Approximations for the Minimum Common Integer Partition Problem
260-271
On Pseudorandom Generators with Linear Stretch in NC0
272-279
A Fast Random Sampling Algorithm for Sparsifying Matrices
280-291
The Effect of Boundary Conditions on Mixing Rates of Markov Chains
292-303
Adaptive Sampling and Fast Low-Rank Matrix Approximation
304-315
Robust Local Testability of Tensor Products of LDPC Codes
316-326
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
327-338
Dobrushin Conditions and Systematic Scan
339-350
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
351-362
Robust Mixing
363-374
Approximating Average Parameters of Graphs
375-385
Local Decoding and Testing for Homomorphisms
386-397
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
398-409
Randomness-Efficient Sampling Within NC1
410-425
Monotone Circuits for the Majority Function
426-437
Space Complexity vs. Query Complexity
438-449
Consistency of Local Density Matrices Is QMA-Complete
450-461
On Bounded Distance Decoding for General Lattices
462-474
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques
475-486
Distance Approximation in Bounded-Degree and General Sparse Graphs
487-498
Fractional Matching Via Balls-and-Bins
499-507
A Randomized Solver for Linear Systems with Exponential Convergence
508-519
Maintaining External Memory Efficient Hash Tables
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