Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings / edited by Maria Serna, Ronen Shaltiel, Klaus Jansen, José Rolim.

Saved in:
Bibliographic Details
Corporate Author: SpringerLink (Online service)
Other Authors: Serna, Maria (Editor), Shaltiel, Ronen (Editor), Jansen, Klaus (Editor), Rolim, José (Editor)
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2010.
Edition:1st ed. 2010.
Series:Theoretical Computer Science and General Issues ; 6302
Springer eBook Collection.
Subjects:
Computer programming.
Computer communication systems.
Computers.
Algorithms.
Computer science—Mathematics.
Data structures (Computer science).
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • Contributed Talks of APPROX
  • Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
  • Improved Inapproximability for Submodular Maximization
  • Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
  • Submodular Secretary Problem and Extensions
  • Approximation Algorithms for Min-Max Generalization Problems
  • Min-Power Strong Connectivity
  • The Complexity of Approximately Counting Stable Matchings
  • Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
  • Approximating Linear Threshold Predicates
  • Approximating Sparsest Cut in Graphs of Bounded Treewidth
  • On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
  • Vertex Sparsifiers: New Results from Old Techniques
  • PTAS for Weighted Set Cover on Unit Squares
  • Improved Lower Bounds for the Universal and a priori TSP
  • Proximity Algorithms for Nearly-Doubling Spaces
  • Matrix Sparsification and the Sparse Null Space Problem
  • The Checkpoint Problem
  • The Euclidean Distortion of Flat Tori
  • Online Embeddings
  • Approximation Algorithms for Intersection Graphs
  • An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs
  • Improved Algorithm for the Half-Disjoint Paths Problem
  • Approximate Lasserre Integrality Gap for Unique Games
  • Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses
  • Maximum Flows on Disjoint Paths
  • Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
  • How to Schedule When You Have to Buy Your Energy
  • Improving Integrality Gaps via Chvátal-Gomory Rounding
  • Contributed Talks of RANDOM
  • Uniform Derandomization from Pathetic Lower Bounds
  • Testing Boolean Function Isomorphism
  • Better Size Estimation for Sparse Matrix Products
  • Low Rate Is Insufficient for Local Testability
  • Reconstruction Threshold for the Hardcore Model
  • Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
  • Monotonicity Testing and Shortest-Path Routing on the Cube
  • Better Gap-Hamming Lower Bounds via Better Round Elimination
  • Propagation Connectivity of Random Hypergraphs
  • Improved Pseudorandom Generators for Depth 2 Circuits
  • The Structure of Winning Strategies in Parallel Repetition Games
  • Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries
  • Periodicity in Streams
  • Rumor Spreading on Random Regular Graphs and Expanders
  • On Testing Computability by Small Width OBDDs
  • Learning and Lower Bounds for AC 0 with Threshold Gates
  • Liftings of Tree-Structured Markov Chains
  • Constructive Proofs of Concentration Bounds
  • Almost-Euclidean Subspaces of via Tensor Products: A Simple Approach to Randomness Reduction
  • Testing Outerplanarity of Bounded Degree Graphs
  • Two-Source Extractors Secure against Quantum Adversaries
  • Locally Testable vs. Locally Decodable Codes
  • Differential Privacy and the Fat-Shattering Dimension of Linear Queries
  • Two Theorems on List Decoding
  • Delaying Satisfiability for Random 2SAT
  • Improved Rounding for Parallel Repeated Unique Games
  • A Query Efficient Non-adaptive Long Code Test with Perfect Completeness
  • Relativized Worlds without Worst-Case to Average-Case Reductions for NP
  • A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field.

Similar Items