LEADER 05786nam 2200625Ia 450 001 9910484749503321 005 20200520144314.0 010 $a1-280-38852-8 010 $a9786613566447 010 $a3-642-15369-0 024 7 $a10.1007/978-3-642-15369-3 035 $a(CKB)2670000000036401 035 $a(SSID)ssj0000446302 035 $a(PQKBManifestationID)11297662 035 $a(PQKBTitleCode)TC0000446302 035 $a(PQKBWorkID)10495992 035 $a(PQKB)11323440 035 $a(DE-He213)978-3-642-15369-3 035 $a(MiAaPQ)EBC3065732 035 $a(PPN)149018363 035 $a(EXLCZ)992670000000036401 100 $a20100901d2010 uy 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aApproximation, randomization, and combinatorial optimization $ealgorithms and techniques ; 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010 ; proceedings /$fMaria Serna ... [et al.] (eds.) 205 $a1st ed. 2010. 210 $aBerlin ;$aNew York $cSpringer$dc2010 215 $a1 online resource (XIII, 782 p. 54 illus.) 225 1 $aLecture notes in computer science,$x0302-9743 ;$v6302 225 1 $aLNCS sublibrary. SL 1, Theoretical computer science and general issues 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-642-15368-2 320 $aIncludes bibliographical references and index. 327 $aContributed 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. 410 0$aLecture notes in computer science ;$v6302. 410 0$aLNCS sublibrary.$nSL 1,$pTheoretical computer science and general issues. 517 3 $aAPPROX 2010 517 3 $aRANDOM 2010 606 $aComputer algorithms$vCongresses 606 $aComputer science$xStatistical methods$vCongresses 615 0$aComputer algorithms 615 0$aComputer science$xStatistical methods 676 $a005.1 701 $aSerna$b Maria$f1959-$01221274 712 12$aInternational Workshop on Randomization and Computation$d(14th :$f2010 :$eBarcelona, Spain) 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484749503321 996 $aApproximation, randomization, and combinatorial optimization$94192240 997 $aUNINA