Series |
Lecture notes in computer science ; 1444 Lecture notes in computer science 1444. ^A466336
|
Contents |
Approximations of independent sets in graphs / Magnús M. Halldórsson -- Using linear programming in the design and analysis of approximation algorithms : two illustrative problems / David B. Shmoys -- The steiner tree problem and its generalizations / Vijay V. Vazirani -- Approximation schemes for covering and scheduling on related machines / Yossi Azar and Leah Epstein -- One for the price of two : a unified approach for approximating covering problems / Reuven Bar-Yehuda -- Approximation of geometric dispersion problems / Christoph Baur and Sándor P. Fekete --Approximating k-outconnected subgraph problems / Joseph Cheriyan, Tibor Jordán and Zeev Nutov -- Lower bounds for on-line scheduling with precedence constraints on identical machines / Leah Epstein -- Instant recognition of half integrality and 2-approximations / Dorit S. Hochbaum -- The t-vertex cover problem : extending the half integrality framework with budget constraints / Dorit S. Hochbaum -- A new fully polynomial approximation scheme for the knapsack problem / Hans Kellerer and Ulrich Pferschy -- On the hardness of approximating spanners / Guy Kortsarz -- Approximating circular arc colouring and bandwith allocation in all-optical ring networks / Vijay Kumar -- Approximating maximum independent set in k-clique-free graphs / Ingo Schiermeyer -- Approximating an interval scheduling problem / Frits C.R. Spieksma -- Finding dense subgraphs with semidefinite programming / Anand Srivastav and Katja Wolf -- Best possible approximation algorithm for MAX SAT with cardinality constraint / Maxim I. Sviridenko. |
General note | Selected papers from APPROX '98, held July 18-19, 1998, University of Aalborg, Denmark, in conjunction with ICALP '98. |
Bibliography note | Includes bibliographical references and index. |
LCCN | 98034217 |
ISBN | 3540647368 (softcover :alk. paper) |