Approximation Algorithms for Combinatorial Optimization

Inhaltsverzeichnis

• Invited Talks.
• Approximation Algorithms That Take Advice.
• Instant Recognition of Polynomial Time Solvability, Half Integrality, and 2-Approximations.
• Scheduling under Uncertainty: Optimizing against a Randomizing Adversary.
• Approximation Algorithms for Facility Location Problems.
• Contributed Talks.
• An Approximation Algorithm for MAX DICUT with Given Sizes of Parts.
• Maximizing Job Benefits On-Line.
• Variable Length Sequencing with Two Lengths.
• Randomized Path Coloring on Binary Trees.
• Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem.
• Greedy Approximation Algorithms for Finding Dense Components in a Graph.
• Online Real-Time Preemptive Scheduling of Jobs with Deadlines.
• On the Relative Complexity of Approximate Counting Problems.
• On the Hardness of Approximating NP Witnesses.
• Maximum Dispersion and Geometric Maximum Weight Cliques.
• New Results for Online Page Replication.
• Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.
• Approximation Algorithms for a Capacitated Network Design Problem.
• An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem.
• Improved Approximations for Tour and Tree Covers.
• Approximating Node Connectivity Problems via Set Covers.
• Rectangle Tiling.
• Primal-Dual Approaches to the Steiner Problem.
• On the Inapproximability of Broadcasting Time.
• Polynomial Time Approximation Schemes for Class-Constrained Packing Problems.
• Partial Servicing of On-Line Jobs.
• Factor 4/3 Approximations for Minimum 2-Connected Subgraphs.