Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques : 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004 and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA August 22-24, 2004 , Proceedings / edited by Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron.

Format:

Book

Contributor:

Jansen, Klaus, editor.

Khanna, Sanjeev, editor.

Rolim, José D. P., editor.

Ron, Dana, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

Lecture notes in computer science 0302-9743 ; 3122.

Lecture Notes in Computer Science, 0302-9743 ; 3122

Language:

English

Subjects (All):

Computers.

Computer science.

Algorithms.

Computer science--Mathematics.

Numerical analysis.

Theory of Computation.

Computer Science, general.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Numeric Computing.

Local Subjects:

Theory of Computation.

Computer Science, general.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Numeric Computing.

Algorithms.

Physical Description:

1 online resource (X, 434 pages).

Edition:

First edition 2004.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2004.

System Details:

text file PDF

Contents:

Contributed Talks of APPROX

Designing Networks with Existing Traffic to Support Fast Restoration

Simultaneous Source Location

Computationally-Feasible Truthful Auctions for Convex Bundles

Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks

On the Crossing Spanning Tree Problem

A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One

Maximum Coverage Problem with Group Budget Constraints and Applications

The Greedy Algorithm for the Minimum Common String Partition Problem

Approximating Additive Distortion of Embeddings into Line Metrics

Polylogarithmic Inapproximability of the Radio Broadcast Problem

On Systems of Linear Equations with Two Variables per Equation

An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case

Cost-Sharing Mechanisms for Network Design

Approximating Max k CSP Using Random Restrictions

Approximation Schemes for Broadcasting in Heterogenous Networks

Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks

Convergence Issues in Competitive Games

Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem

Min-Max Multiway Cut

Contributed Talks of RANDOM

The Chromatic Number of Random Regular Graphs

Estimating the Distance to a Monotone Function

Edge Coloring with Delays

Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption

The Sketching Complexity of Pattern Matching

Non-Abelian Homomorphism Testing, and Distributions Close to Their Self-convolutions

Robust Locally Testable Codes and Products of Codes

A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes

Strong Refutation Heuristics for Random k-SAT

Counting Connected Graphs and Hypergraphs via the Probabilistic Method

Improved Randomness Extraction from Two Independent Sources

The Diameter of Randomly Perturbed Digraphs and Some Applications

Maximum Weight Independent Sets and Matchings in Sparse Random Graphs

Estimating Frequency Moments of Data Streams Using Random Linear Combinations

Fooling Parity Tests with Parity Gates

Distribution-Free Connectivity Testing

Testing the Independence Number of Hypergraphs

A Note on Approximate Counting for k-DNF.

Other Format:

Printed edition:

ISBN:

978-3-540-27821-4

9783540278214

Access Restriction:

Restricted for use by site license.