En savoir plus sur le livre
This collection features a variety of invited and contributed talks focused on approximation algorithms and their applications across different domains. Key topics include the development of algorithms that utilize advice for approximation, instant recognition of polynomial time solvability, and strategies for scheduling under uncertainty against randomizing adversaries. Contributions also explore facility location problems and specific algorithms for MAX DICUT with predetermined part sizes. Other discussions cover maximizing job benefits in online scenarios, variable length sequencing, and randomized path coloring in binary trees. The collection delves into wavelength rerouting in optical networks, greedy approximation methods for dense components in graphs, and online real-time preemptive scheduling of jobs with deadlines. It addresses the complexity of approximate counting problems and the challenges of approximating NP witnesses. Additional insights include maximum dispersion, geometric maximum weight cliques, and new results in online page replication. The works presented also tackle inapproximability for set splitting and satisfiability problems without mixed clauses, capacitated network design, and fault-tolerant metric facility location. Improved approximations for tour and tree covers, node connectivity via set covers, rectangle tiling, and primal-dual approaches to the Steiner problem are discussed, along with the
Achat du livre
Approximation algorithms for combinatorial optimization, Klaus Jansen
- Langue
- Année de publication
- 2000
- product-detail.submit-box.info.binding
- (souple)
Modes de paiement
Personne n'a encore évalué .