↓ 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 Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
  3. Altmetric Badge
    Chapter 2 Improved Inapproximability for Submodular Maximization
  4. Altmetric Badge
    Chapter 3 Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
  5. Altmetric Badge
    Chapter 4 Submodular Secretary Problem and Extensions
  6. Altmetric Badge
    Chapter 5 Approximation Algorithms for Min-Max Generalization Problems
  7. Altmetric Badge
    Chapter 6 Min-Power Strong Connectivity
  8. Altmetric Badge
    Chapter 7 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
  9. Altmetric Badge
    Chapter 8 Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
  10. Altmetric Badge
    Chapter 9 Approximating Linear Threshold Predicates
  11. Altmetric Badge
    Chapter 10 Approximating Sparsest Cut in Graphs of Bounded Treewidth
  12. Altmetric Badge
    Chapter 11 On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
  13. Altmetric Badge
    Chapter 12 Vertex Sparsifiers: New Results from Old Techniques
  14. Altmetric Badge
    Chapter 13 PTAS for Weighted Set Cover on Unit Squares
  15. Altmetric Badge
    Chapter 14 Improved Lower Bounds for the Universal and a priori TSP
  16. Altmetric Badge
    Chapter 15 Proximity Algorithms for Nearly-Doubling Spaces
  17. Altmetric Badge
    Chapter 16 Matrix Sparsification and the Sparse Null Space Problem
  18. Altmetric Badge
    Chapter 17 The Checkpoint Problem
  19. Altmetric Badge
    Chapter 18 The Euclidean Distortion of Flat Tori
  20. Altmetric Badge
    Chapter 19 Online Embeddings
  21. Altmetric Badge
    Chapter 20 Approximation Algorithms for Intersection Graphs
  22. Altmetric Badge
    Chapter 21 An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs
  23. Altmetric Badge
    Chapter 22 Improved Algorithm for the Half-Disjoint Paths Problem
  24. Altmetric Badge
    Chapter 23 Approximate Lasserre Integrality Gap for Unique Games
  25. Altmetric Badge
    Chapter 24 Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses
  26. Altmetric Badge
    Chapter 25 Maximum Flows on Disjoint Paths
  27. Altmetric Badge
    Chapter 26 Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
  28. Altmetric Badge
    Chapter 27 How to Schedule When You Have to Buy Your Energy
  29. Altmetric Badge
    Chapter 28 Improving Integrality Gaps via Chvátal-Gomory Rounding
  30. Altmetric Badge
    Chapter 29 Uniform Derandomization from Pathetic Lower Bounds
  31. Altmetric Badge
    Chapter 30 Testing Boolean Function Isomorphism
  32. Altmetric Badge
    Chapter 31 Better Size Estimation for Sparse Matrix Products
  33. Altmetric Badge
    Chapter 32 Low Rate Is Insufficient for Local Testability
  34. Altmetric Badge
    Chapter 33 Reconstruction Threshold for the Hardcore Model
  35. Altmetric Badge
    Chapter 34 Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
  36. Altmetric Badge
    Chapter 35 Monotonicity Testing and Shortest-Path Routing on the Cube
  37. Altmetric Badge
    Chapter 36 Better Gap-Hamming Lower Bounds via Better Round Elimination
  38. Altmetric Badge
    Chapter 37 Propagation Connectivity of Random Hypergraphs
  39. Altmetric Badge
    Chapter 38 Improved Pseudorandom Generators for Depth 2 Circuits
  40. Altmetric Badge
    Chapter 39 The Structure of Winning Strategies in Parallel Repetition Games
  41. Altmetric Badge
    Chapter 40 Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries
  42. Altmetric Badge
    Chapter 41 Periodicity in Streams
  43. Altmetric Badge
    Chapter 42 Rumor Spreading on Random Regular Graphs and Expanders
  44. Altmetric Badge
    Chapter 43 On Testing Computability by Small Width OBDDs
  45. Altmetric Badge
    Chapter 44 Learning and Lower Bounds for AC 0 with Threshold Gates
  46. Altmetric Badge
    Chapter 45 Liftings of Tree-Structured Markov Chains
  47. Altmetric Badge
    Chapter 46 Constructive Proofs of Concentration Bounds
  48. Altmetric Badge
    Chapter 47 Almost-Euclidean Subspaces of $\ell_1^N$ via Tensor Products: A Simple Approach to Randomness Reduction
  49. Altmetric Badge
    Chapter 48 Testing Outerplanarity of Bounded Degree Graphs
  50. Altmetric Badge
    Chapter 49 Two-Source Extractors Secure against Quantum Adversaries
  51. Altmetric Badge
    Chapter 50 Locally Testable vs. Locally Decodable Codes
  52. Altmetric Badge
    Chapter 51 Differential Privacy and the Fat-Shattering Dimension of Linear Queries
  53. Altmetric Badge
    Chapter 52 Two Theorems on List Decoding
  54. Altmetric Badge
    Chapter 53 Delaying Satisfiability for Random 2SAT
  55. Altmetric Badge
    Chapter 54 Improved Rounding for Parallel Repeated Unique Games
  56. Altmetric Badge
    Chapter 55 A Query Efficient Non-adaptive Long Code Test with Perfect Completeness
  57. Altmetric Badge
    Chapter 56 Relativized Worlds without Worst-Case to Average-Case Reductions for NP
  58. Altmetric Badge
    Chapter 57 A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
Attention for Chapter 9: Approximating Linear Threshold Predicates
Altmetric Badge

About this Attention Score

  • In the top 25% of all research outputs scored by Altmetric
  • Good Attention Score compared to outputs of the same age (77th percentile)
  • Above-average Attention Score compared to outputs of the same age and source (64th percentile)

Mentioned by

blogs
1 blog

Citations

dimensions_citation
5 Dimensions
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
Approximating Linear Threshold Predicates
Chapter number 9
Book title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Published in
Lecture notes in computer science, February 2016
DOI 10.1007/978-3-642-15369-3_9
Book ISBNs
978-3-64-215368-6, 978-3-64-215369-3
Authors

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson

Attention Score in Context

Attention Score in Context

This research output has an Altmetric Attention Score of 6. This is our high-level measure of the quality and quantity of online attention that it has received. This Attention Score, as well as the ranking and number of research outputs shown below, was calculated when the research output was last mentioned on 13 March 2014.
All research outputs
#5,426,703
of 22,747,498 outputs
Outputs from Lecture notes in computer science
#1,697
of 8,126 outputs
Outputs of similar age
#88,464
of 396,715 outputs
Outputs of similar age from Lecture notes in computer science
#183
of 510 outputs
Altmetric has tracked 22,747,498 research outputs across all sources so far. Compared to these this one has done well and is in the 76th percentile: it's in the top 25% of all research outputs ever tracked by Altmetric.
So far Altmetric has tracked 8,126 research outputs from this source. They receive a mean Attention Score of 5.0. This one has done well, scoring higher than 79% of its peers.
Older research outputs will score higher simply because they've had more time to accumulate mentions. To account for age we can compare this Altmetric Attention Score to the 396,715 tracked outputs that were published within six weeks on either side of this one in any source. This one has done well, scoring higher than 77% of its contemporaries.
We're also able to compare this research output to 510 others from the same source and published within six weeks on either side of this one. This one has gotten more attention than average, scoring higher than 64% of its contemporaries.