Willkommen, schön sind Sie da!
Logo Ex Libris

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

  • E-Book (pdf)
  • 782 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
Inhalt Contributed Talks of APPROX.- Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem.- Improved ... Weiterlesen
E-Books ganz einfach mit der kostenlosen Ex Libris-Reader-App lesen. Hiererhalten Sie Ihren Download-Link.
CHF 153.50
Download steht sofort bereit
Informationen zu E-Books
E-Books eignen sich auch für mobile Geräte (sehen Sie dazu die Anleitungen).
E-Books von Ex Libris sind mit Adobe DRM kopiergeschützt: Erfahren Sie mehr.
Weitere Informationen finden Sie hier.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

Inhalt

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.

Produktinformationen

Titel: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Untertitel: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings
Editor:
EAN: 9783642153693
Digitaler Kopierschutz: Wasserzeichen
Format: E-Book (pdf)
Hersteller: Springer Berlin Heidelberg
Genre: IT & Internet
Anzahl Seiten: 782
Veröffentlichung: 27.08.2010
Dateigrösse: 11.1 MB

Weitere Bände aus der Buchreihe "Theoretical Computer Science and General Issues"