↓ Skip to main content

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Overview of attention for book
Cover of 'Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 On Nontrivial Approximation of CSPs
  3. Altmetric Badge
    Chapter 2 Analysis of Algorithms on the Cores of Random Graphs
  4. Altmetric Badge
    Chapter 3 Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
  5. Altmetric Badge
    Chapter 4 Approximating Precedence-Constrained Single Machine Scheduling by Coloring
  6. Altmetric Badge
    Chapter 5 Minimizing Setup and Beam-On Times in Radiation Therapy
  7. Altmetric Badge
    Chapter 6 On the Value of Preemption in Scheduling
  8. Altmetric Badge
    Chapter 7 An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs
  9. Altmetric Badge
    Chapter 8 Tight Results on Minimum Entropy Set Cover
  10. Altmetric Badge
    Chapter 9 A Tight Lower Bound for the Steiner Point Removal Problem on Trees
  11. Altmetric Badge
    Chapter 10 Single-Source Stochastic Routing
  12. Altmetric Badge
    Chapter 11 An O (log n ) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
  13. Altmetric Badge
    Chapter 12 Online Algorithms to Minimize Resource Reallocations and Network Communication
  14. Altmetric Badge
    Chapter 13 Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
  15. Altmetric Badge
    Chapter 14 Combinatorial Algorithms for Data Migration to Minimize Average Completion Time
  16. Altmetric Badge
    Chapter 15 LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times
  17. Altmetric Badge
    Chapter 16 Approximating Buy-at-Bulk and Shallow-Light k -Steiner Trees
  18. Altmetric Badge
    Chapter 17 Improved Algorithms for Data Migration
  19. Altmetric Badge
    Chapter 18 Approximation Algorithms for Graph Homomorphism Problems
  20. Altmetric Badge
    Chapter 19 Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem
  21. Altmetric Badge
    Chapter 20 Hardness of Preemptive Finite Capacity Dial-a-Ride
  22. Altmetric Badge
    Chapter 21 Minimum Vehicle Routing with a Common Deadline
  23. Altmetric Badge
    Chapter 22 Stochastic Combinatorial Optimization with Controllable Risk Aversion Level
  24. Altmetric Badge
    Chapter 23 Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
  25. Altmetric Badge
    Chapter 24 Better Approximations for the Minimum Common Integer Partition Problem
  26. Altmetric Badge
    Chapter 25 On Pseudorandom Generators with Linear Stretch in NC 0  
  27. Altmetric Badge
    Chapter 26 A Fast Random Sampling Algorithm for Sparsifying Matrices
  28. Altmetric Badge
    Chapter 27 The Effect of Boundary Conditions on Mixing Rates of Markov Chains
  29. Altmetric Badge
    Chapter 28 Adaptive Sampling and Fast Low-Rank Matrix Approximation
  30. Altmetric Badge
    Chapter 29 Robust Local Testability of Tensor Products of LDPC Codes
  31. Altmetric Badge
    Chapter 30 Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
  32. Altmetric Badge
    Chapter 31 Dobrushin Conditions and Systematic Scan
  33. Altmetric Badge
    Chapter 32 Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
  34. Altmetric Badge
    Chapter 33 Robust Mixing
  35. Altmetric Badge
    Chapter 34 Approximating Average Parameters of Graphs
  36. Altmetric Badge
    Chapter 35 Local Decoding and Testing for Homomorphisms
  37. Altmetric Badge
    Chapter 36 Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
  38. Altmetric Badge
    Chapter 37 Randomness-Efficient Sampling Within NC 1
  39. Altmetric Badge
    Chapter 38 Monotone Circuits for the Majority Function
  40. Altmetric Badge
    Chapter 39 Space Complexity vs. Query Complexity
  41. Altmetric Badge
    Chapter 40 Consistency of Local Density Matrices Is QMA-Complete
  42. Altmetric Badge
    Chapter 41 On Bounded Distance Decoding for General Lattices
  43. Altmetric Badge
    Chapter 42 Threshold Functions for Asymmetric Ramsey Properties Involving Cliques
  44. Altmetric Badge
    Chapter 43 Distance Approximation in Bounded-Degree and General Sparse Graphs
  45. Altmetric Badge
    Chapter 44 Fractional Matching Via Balls-and-Bins
  46. Altmetric Badge
    Chapter 45 A Randomized Solver for Linear Systems with Exponential Convergence
  47. Altmetric Badge
    Chapter 46 Maintaining External Memory Efficient Hash Tables
Attention for Chapter 15: LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times
Altmetric Badge

Citations

dimensions_citation
8 Dimensions

Readers on

mendeley
10 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Chapter title
LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times
Chapter number 15
Book title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Published by
Springer, Berlin, Heidelberg, January 2006
DOI 10.1007/11830924_15
Book ISBNs
978-3-54-038044-3, 978-3-54-038045-0
Authors

Alexander Grigoriev, Maxim Sviridenko, Marc Uetz, Grigoriev, Alexander, Sviridenko, Maxim, Uetz, Marc

Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 10 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
Colombia 2 20%
India 1 10%
Unknown 7 70%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 3 30%
Researcher 3 30%
Student > Bachelor 1 10%
Other 1 10%
Student > Master 1 10%
Other 1 10%
Readers by discipline Count As %
Computer Science 4 40%
Mathematics 2 20%
Business, Management and Accounting 2 20%
Engineering 2 20%