000 04181nam a22006375i 4500
001 978-3-540-69067-2
003 DE-He213
005 20240423132443.0
007 cr nn 008mamaa
008 121227s1998 gw | s |||| 0|eng d
020 _a9783540690672
_9978-3-540-69067-2
024 7 _a10.1007/BFb0053958
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
245 1 0 _aApproximation Algorithms for Combinatorial Optimization
_h[electronic resource] :
_bInternational Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings /
_cedited by Klaus Jansen, Jose Rolim.
250 _a1st ed. 1998.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c1998.
300 _aIX, 207 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Computer Science,
_x1611-3349 ;
_v1444
505 0 _aApproximations of independent sets in graphs -- Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems -- The Steiner tree problem and its generalizations -- Approximation schemes for covering and scheduling in related machines -- One for the price of two: A unified approach for approximating covering problems -- Approximation of geometric dispersion problems -- Approximating k-outconnected subgraph problems -- Lower bounds for on-line scheduling with precedence constraints on identical machines -- Instant recognition of half integrality and 2-approximations -- The t-vertex cover problem: Extending the half integrality framework with budget constraints -- A new fully polynomial approximation scheme for the knapsack problem -- On the hardness of approximating spanners -- Approximating circular arc colouring and bandwidth allocation in all-optical ring networks -- Approximating maximum independent set in k-clique-free graphs -- Approximating an interval scheduling problem -- Finding dense subgraphs with semidefinite programming -- Best possible approximation algorithm for MAX SAT with cardinality constraint.
520 _aThis book constitutes the refereed proceedings of the International Workshop on Approximation Algorithms for Combinatorical Optimization, APPROX'98, held in conjunction with ICALP'98 in Aalborg, Denmark, in July 1998. The volume presents 14 revised full papers together with three invited papers selected from 37 submissions. The papers address the design and analysis of approximation algorithms, inapproximability results, on-line problems, randomization techniques, average-case analysis, approximation classes, scheduling problems, routing and flow problems, coloring and partitioning, cuts and connectivity, packing and covering, geometric problems, network design, and various applications.
650 0 _aComputer science.
650 0 _aAlgorithms.
650 0 _aComputer science
_xMathematics.
650 0 _aDiscrete mathematics.
650 0 _aMathematical optimization.
650 0 _aCalculus of variations.
650 0 _aComputer graphics.
650 1 4 _aTheory of Computation.
650 2 4 _aAlgorithms.
650 2 4 _aDiscrete Mathematics in Computer Science.
650 2 4 _aCalculus of Variations and Optimization.
650 2 4 _aComputer Graphics.
700 1 _aJansen, Klaus.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aRolim, Jose.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540647362
776 0 8 _iPrinted edition:
_z9783662191989
830 0 _aLecture Notes in Computer Science,
_x1611-3349 ;
_v1444
856 4 0 _uhttps://doi.org/10.1007/BFb0053958
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
912 _aZDB-2-BAE
942 _cSPRINGER
999 _c187929
_d187929