Approximation, randomization and combinatorial optimization

Más información sobre el libro

This collection features a range of contributed talks covering various topics in approximation algorithms and network design. It includes discussions on designing networks to support fast restoration, simultaneous source location, and computationally-feasible truthful auctions for convex bundles. The book addresses randomized approximation algorithms for set multicover problems, particularly in the context of reverse engineering protein and gene networks. Key topics also include a 3/4-approximation algorithm for the maximum asymmetric traveling salesman problem, maximum coverage with group budget constraints, and the greedy algorithm for minimum common string partitioning. Further exploration includes approximating additive distortion in line metrics, polylogarithmic inapproximability of the radio broadcast problem, and auction-based market equilibrium algorithms. The text discusses cost-sharing mechanisms for network design, approximation schemes for broadcasting in heterogeneous networks, and convergence issues in competitive games. Other significant contributions involve semidefinite relaxations for linear ordering problems, min-max multiway cuts, and the chromatic number of random regular graphs. The collection also delves into estimating distances to monotone functions, edge coloring with delays, and robust locally testable codes. Topics such as stateful implementations of random functions, strong refutation heuristics