000 06535nam a22006375i 4500
001 978-3-540-85363-3
003 DE-He213
005 20240730195425.0
007 cr nn 008mamaa
008 100301s2008 gw | s |||| 0|eng d
020 _a9783540853633
_9978-3-540-85363-3
024 7 _a10.1007/978-3-540-85363-3
_2doi
050 4 _aQA76.6-76.66
072 7 _aUM
_2bicssc
072 7 _aCOM051000
_2bisacsh
072 7 _aUM
_2thema
082 0 4 _a005.11
_223
245 1 0 _aApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
_h[electronic resource] :
_b11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008 /
_cedited by Ashish Goel, Klaus Jansen, José Rolim, Ronitt Rubinfeld.
250 _a1st ed. 2008.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2008.
300 _aXII, 604 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 ;
_v5171
505 0 _aContributed Talks of APPROX -- Approximating Optimal Binary Decision Trees -- Santa Claus Meets Hypergraph Matchings -- Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction -- Connected Vertex Covers in Dense Graphs -- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies -- Sweeping Points -- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness -- Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks -- Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP -- Approximating Maximum Subgraphs without Short Cycles -- Deterministic 7/8-Approximation for the Metric Maximum TSP -- Inapproximability of Survivable Networks -- Approximating Single Machine Scheduling with Scenarios -- Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity -- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One -- The Directed Minimum Latency Problem -- A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem -- Approximating Directed Weighted-Degree Constrained Networks -- A Constant Factor Approximation for Minimum ?-Edge-Connected k-Subgraph with Metric Costs -- Budgeted Allocations in the Full-Information Setting -- Contributed Talks of RANDOM -- Optimal Random Matchings on Trees and Applications -- Small Sample Spaces Cannot Fool Low Degree Polynomials -- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size -- Tensor Products of Weakly Smooth Codes Are Robust -- On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs -- Improved Bounds for Testing Juntas -- The Complexity of Distinguishing MarkovRandom Fields -- Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms -- Tight Bounds for Hashing Block Sources -- Improved Separations between Nondeterministic and Randomized Multiparty Communication -- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs -- On the Query Complexity of Testing Orientations for Being Eulerian -- Approximately Counting Embeddings into Random Graphs -- Increasing the Output Length of Zero-Error Dispersers -- Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals -- The Complexity of Local List Decoding -- Limitations of Hardness vs. Randomness under Uniform Reductions -- Learning Random Monotone DNF -- Breaking the ?-Soundness Bound of the Linearity Test over GF(2) -- Dense Fast Random Projections and Lean Walsh Transforms -- Near Optimal Dimensionality Reductions That Preserve Volumes -- Sampling Hypersurfaces through Diffusion -- A 2-Source Almost-Extractor for Linear Entropy -- Extractors for Three Uneven-Length Sources -- The Power of Choice in a Generalized Pólya Urn Model -- Corruption and Recovery-Efficient Locally Decodable Codes -- Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets.
520 _aThis book constitutes the joint refereed proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and the 12th International Workshop on Randomization and Computation, RANDOM 2008, held in Boston, MA, USA, in August 2008. The 20 revised full papers of the APPROX 2008 workshop were carefully reviewed and selected from 42 submissions and focus on algorithmic and complexity issues surrounding the development of efficient approximate solutions to computationally difficult problems. RANDOM 2008 is concerned with applications of randomness to computational and combinatorial problems and accounts for 27 revised full papers, also diligently reviewed and selected out of 52 workshop submissions.
650 0 _aComputer programming.
_94169
650 0 _aComputer science.
_99832
650 0 _aAlgorithms.
_93390
650 0 _aComputer science
_xMathematics.
_93866
650 0 _aDiscrete mathematics.
_912873
650 0 _aNumerical analysis.
_94603
650 1 4 _aProgramming Techniques.
_9160238
650 2 4 _aTheory of Computation.
_9160239
650 2 4 _aAlgorithms.
_93390
650 2 4 _aDiscrete Mathematics in Computer Science.
_931837
650 2 4 _aNumerical Analysis.
_94603
700 1 _aGoel, Ashish.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9160240
700 1 _aJansen, Klaus.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9160241
700 1 _aRolim, José.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9160242
700 1 _aRubinfeld, Ronitt.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9160243
710 2 _aSpringerLink (Online service)
_9160244
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540853626
776 0 8 _iPrinted edition:
_z9783540853961
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5171
_9160245
856 4 0 _uhttps://doi.org/10.1007/978-3-540-85363-3
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c95624
_d95624