000 05125nam a22005775i 4500
001 978-3-540-31874-3
003 DE-He213
005 20240730181410.0
007 cr nn 008mamaa
008 100928s2005 gw | s |||| 0|eng d
020 _a9783540318743
_9978-3-540-31874-3
024 7 _a10.1007/11538462
_2doi
050 4 _aQA76.9.A43
072 7 _aUMB
_2bicssc
072 7 _aCOM051300
_2bisacsh
072 7 _aUMB
_2thema
082 0 4 _a518.1
_223
245 1 0 _aApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
_h[electronic resource] :
_b8th International Workshop on Approximation Algorithms for Compinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings /
_cedited by Chandra Chekuri, Klaus Jansen, José D.P. Rolim, Luca Trevisan.
250 _a1st ed. 2005.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2005.
300 _aXI, 495 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v3624
505 0 _aContributed Talks of APPROX -- The Network as a Storage Device: Dynamic Routing with Bounded Buffers -- Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT -- What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs -- A Rounding Algorithm for Approximating Minimum Manhattan Networks -- Packing Element-Disjoint Steiner Trees -- Approximating the Bandwidth of Caterpillars -- Where's the Winner? Max-Finding and Sorting with Metric Costs -- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization -- The Complexity of Making Unique Choices: Approximating 1-in-k SAT -- Approximating the Distortion -- Approximating the Best-Fit Tree Under L p Norms -- Beating a Random Assignment -- Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints -- Approximation Algorithms for Network Design and Facility Location with Service Capacities -- Finding Graph Matchings in Data Streams -- A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses -- Efficient Approximation of Convex Recolorings -- Approximation Algorithms for Requirement Cut on Graphs -- Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems -- Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy -- Contributed Talks of RANDOM -- Bounds for Error Reduction with Few Quantum Queries -- Sampling Bounds for Stochastic Optimization -- An Improved Analysis of Mergers -- Finding a Maximum Independent Set in a Sparse Random Graph -- On the Error Parameter of Dispersers -- Tolerant Locally Testable Codes -- A Lower Bound on List Size for List Decoding -- A Lower Bound for Distribution-Free Monotonicity Testing -- On Learning Random DNF Formulas Under the Uniform Distribution.-Derandomized Constructions of k-Wise (Almost) Independent Permutations -- Testing Periodicity -- The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem -- The Online Clique Avoidance Game on Random Graphs -- A Generating Function Method for the Average-Case Analysis of DPLL -- A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas -- Mixing Points on a Circle -- Derandomized Squaring of Graphs -- Tight Bounds for String Reconstruction Using Substring Queries -- Reconstructive Dispersers and Hitting Set Generators -- The Tensor Product of Two Codes Is Not Necessarily Robustly Testable -- Fractional Decompositions of Dense Hypergraphs.
650 0 _aAlgorithms.
_93390
650 0 _aNumerical analysis.
_94603
650 0 _aComputer science
_xMathematics.
_93866
650 0 _aDiscrete mathematics.
_912873
650 1 4 _aAlgorithms.
_93390
650 2 4 _aNumerical Analysis.
_94603
650 2 4 _aDiscrete Mathematics in Computer Science.
_931837
700 1 _aChekuri, Chandra.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9124696
700 1 _aJansen, Klaus.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9124697
700 1 _aRolim, José D.P.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9124698
700 1 _aTrevisan, Luca.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9124699
710 2 _aSpringerLink (Online service)
_9124700
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540282396
776 0 8 _iPrinted edition:
_z9783540814177
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v3624
_9124701
856 4 0 _uhttps://doi.org/10.1007/11538462
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c90874
_d90874