000 05184nam a22005895i 4500
001 978-3-540-45198-3
003 DE-He213
005 20160624101959.0
007 cr nn 008mamaa
008 121227s2003 gw | s |||| 0|eng d
020 _a9783540451983
_9978-3-540-45198-3
024 7 _a10.1007/b11961
_2doi
050 4 _aQA76.9.A43
072 7 _aUMB
_2bicssc
072 7 _aCOM051300
_2bisacsh
082 0 4 _a005.1
_223
245 1 0 _aApproximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
_h[electronic resource] :
_b6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003. Proceedings /
_cedited by Sanjeev Arora, Klaus Jansen, José D. P. Rolim, Amit Sahai.
260 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2003.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2003.
300 _aIX, 411 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v2764
505 0 _aContributed Talks of APPROX -- Correlation Clustering with Partial Information -- Improved Linear Time Approximation Algorithms for Weighted Matchings -- Covering Graphs Using Trees and Stars -- An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor -- Approximation Algorithms for Channel Allocation Problems in Broadcast Networks -- Asymmetry in k-Center Variants -- An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times -- On the Complexity of Approximating k-Dimensional Matching -- Approximating Market Equilibria -- Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem -- On the Hardness of Approximate Multivariate Integration -- A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem -- Approximating Rooted Connectivity Augmentation Problems -- Effective Routing and Scheduling in Adversarial Queueing Networks -- Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement -- An Improved Algorithm for Approximating the Radii of Point Sets -- Contributed Talks of RANDOM -- Testing Low-Degree Polynomials over GF(2) -- Computational Analogues of Entropy -- Bounds on 2-Query Codeword Testing -- The Lovász Number of Random Graphs -- Perfectly Balanced Allocation -- On Extracting Private Randomness over a Public Channel -- High Degree Vertices and Eigenvalues in the Preferential Attachment Graph -- The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems -- Continuous-Time Quantum Walks on the Symmetric Group -- Distribution-Free Property Testing -- On the Graph-Density of Random 0/1-Polytopes -- A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding -- Tight Bounds for Testing Bipartiteness in General Graphs -- Discrete Quantum Walks Hit Exponentially Faster -- Approximate Testing of Visual Properties -- Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances -- A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries.
520 _aThis book constitutes the joint refereed proceedings of the 6th International Workshop on Approximation Algorithms for Optimization Problems, APPROX 2003 and of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, held in Princeton, NY, USA in August 2003. The 33 revised full papers presented were carefully reviewed and selected from 74 submissions. Among the issues addressed are design and analysis of randomized and approximation algorithms, online algorithms, complexity theory, combinatorial structures, error-correcting codes, pseudorandomness, derandomization, network algorithms, random walks, Markov chains, probabilistic proof systems, computational learning, randomness in cryptography, and various applications.
650 0 _aComputer science.
650 0 _aComputer software.
650 0 _aElectronic data processing.
650 0 _aComputational complexity.
650 0 _aAlgorithms.
650 0 _aCombinatorics.
650 1 4 _aComputer Science.
650 2 4 _aAlgorithm Analysis and Problem Complexity.
650 2 4 _aNumeric Computing.
650 2 4 _aDiscrete Mathematics in Computer Science.
650 2 4 _aAlgorithms.
650 2 4 _aCombinatorics.
700 1 _aArora, Sanjeev.
_eeditor.
700 1 _aJansen, Klaus.
_eeditor.
700 1 _aRolim, José D. P.
_eeditor.
700 1 _aSahai, Amit.
_eeditor.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783540407706
786 _dSpringer
830 0 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v2764
856 4 0 _uhttp://dx.doi.org/10.1007/b11961
942 _2EBK5243
_cEBK
999 _c34537
_d34537