↓ Skip to main content

STACS 2005

Overview of attention for book
Cover of 'STACS 2005'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Automorphisms of Finite Rings and Applications to Complexity of Problems
  3. Altmetric Badge
    Chapter 2 Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages
  4. Altmetric Badge
    Chapter 3 Algorithmics in Exponential Time
  5. Altmetric Badge
    Chapter 4 Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics
  6. Altmetric Badge
    Chapter 5 Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms
  7. Altmetric Badge
    Chapter 6 Truthful Approximation Mechanisms for Scheduling Selfish Related Machines
  8. Altmetric Badge
    Chapter 7 Counting in the Two Variable Guarded Logic with Transitivity
  9. Altmetric Badge
    Chapter 8 The Variable Hierarchy of the μ-Calculus Is Strict
  10. Altmetric Badge
    Chapter 9 The Core of a Countably Categorical Structure
  11. Altmetric Badge
    Chapter 10 How Common Can Be Universality for Cellular Automata?
  12. Altmetric Badge
    Chapter 11 Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods
  13. Altmetric Badge
    Chapter 12 On the Decidability of Temporal Properties of Probabilistic Pushdown Automata
  14. Altmetric Badge
    Chapter 13 Deciding Properties of Contract-Signing Protocols
  15. Altmetric Badge
    Chapter 14 Polylog-Time Reductions Decrease Dot-Depth
  16. Altmetric Badge
    Chapter 15 On the Computational Complexity of the Forcing Chromatic Number
  17. Altmetric Badge
    Chapter 16 More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP
  18. Altmetric Badge
    Chapter 17 Three Optimal Algorithms for Balls of Three Colors
  19. Altmetric Badge
    Chapter 18 Cost Sharing and Strategyproof Mechanisms for Set Cover Games
  20. Altmetric Badge
    Chapter 19 On Weighted Balls-into-Bins Games
  21. Altmetric Badge
    Chapter 20 Computing Minimal Multi-homogeneous Bézout Numbers Is Hard
  22. Altmetric Badge
    Chapter 21 Dynamic Complexity Theory Revisited
  23. Altmetric Badge
    Chapter 22 Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
  24. Altmetric Badge
    Chapter 23 Shortest Monotone Descent Path Problem in Polyhedral Terrain
  25. Altmetric Badge
    Chapter 24 Packet Buffering: Randomization Beats Deterministic Algorithms
  26. Altmetric Badge
    Chapter 25 Solving Medium-Density Subset Sum Problems in Expected Polynomial Time
  27. Altmetric Badge
    Chapter 26 Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms
  28. Altmetric Badge
    Chapter 27 Regular Tree Languages Definable in FO
  29. Altmetric Badge
    Chapter 28 Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations
  30. Altmetric Badge
    Chapter 29 Connectivity for Wireless Agents Moving on a Cycle or Grid
  31. Altmetric Badge
    Chapter 30 Improved Algorithms for Dynamic Page Migration
  32. Altmetric Badge
    Chapter 31 Approximate Range Mode and Range Median Queries
  33. Altmetric Badge
    Chapter 32 Topological Automata
  34. Altmetric Badge
    Chapter 33 Minimizing NFA’s and Regular Expressions
  35. Altmetric Badge
    Chapter 34 Increasing Kolmogorov Complexity
  36. Altmetric Badge
    Chapter 35 Kolmogorov-Loveland Randomness and Stochasticity
  37. Altmetric Badge
    Chapter 36 Information Theory in Property Testing and Monotonicity Testing in Higher Dimension
  38. Altmetric Badge
    Chapter 37 On Nash Equilibria in Non-cooperative All-Optical Networks
  39. Altmetric Badge
    Chapter 38 Speed Scaling to Manage Temperature
  40. Altmetric Badge
    Chapter 39 The Complexity of Solving Linear Equations over a Finite Ring
  41. Altmetric Badge
    Chapter 40 A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields
  42. Altmetric Badge
    Chapter 41 Characterizing TC0 in Terms of Infinite Groups
  43. Altmetric Badge
    Chapter 42 Fast Pruning of Geometric Spanners
  44. Altmetric Badge
    Chapter 43 The PIGs Full Monty – A Floor Show of Minimal Separators
  45. Altmetric Badge
    Chapter 44 Centrality Measures Based on Current Flow
  46. Altmetric Badge
    Chapter 45 Varieties of Codes and Kraft Inequality
  47. Altmetric Badge
    Chapter 46 Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes
  48. Altmetric Badge
    Chapter 47 The Power of Commuting with Finite Sets of Words
  49. Altmetric Badge
    Chapter 48 Exact Quantum Algorithms for the Leader Election Problem
  50. Altmetric Badge
    Chapter 49 Robust Polynomials and Quantum Algorithms
  51. Altmetric Badge
    Chapter 50 Quantum Interactive Proofs with Competing Provers
  52. Altmetric Badge
    Chapter 51 Roundings Respecting Hard Constraints
  53. Altmetric Badge
    Chapter 52 Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves
  54. Altmetric Badge
    Chapter 53 Cycle Cover with Short Cycles
  55. Altmetric Badge
    Chapter 54 A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs
  56. Altmetric Badge
    Chapter 55 All-Pairs Nearly 2-Approximate Shortest-Paths in O(n 2 polylog n) Time
  57. Altmetric Badge
    Chapter 56 Pattern Occurrences in Multicomponent Models
  58. Altmetric Badge
    Chapter 57 Automatic Presentations for Finitely Generated Groups
Attention for Chapter 4: Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics
Altmetric Badge

Citations

dimensions_citation
6 Dimensions

Readers on

mendeley
24 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
Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics
Chapter number 4
Book title
STACS 2005
Published by
Springer, Berlin, Heidelberg, February 2005
DOI 10.1007/978-3-540-31856-9_4
Book ISBNs
978-3-54-024998-6, 978-3-54-031856-9
Authors

Carsten Witt

Mendeley readers

Mendeley readers

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

Geographical breakdown

Country Count As %
United Kingdom 1 4%
Unknown 23 96%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 7 29%
Lecturer > Senior Lecturer 2 8%
Lecturer 2 8%
Student > Master 2 8%
Professor > Associate Professor 2 8%
Other 4 17%
Unknown 5 21%
Readers by discipline Count As %
Computer Science 12 50%
Engineering 4 17%
Mathematics 1 4%
Business, Management and Accounting 1 4%
Unspecified 1 4%
Other 0 0%
Unknown 5 21%