000 02495nam a22003618i 4500
001 CR9780511666407
003 UkCbUP
005 20200124160228.0
006 m|||||o||d||||||||
007 cr||||||||||||
008 091217s1997||||enk o ||1 0|eng|d
020 _a9780511666407 (ebook)
020 _z9780521431705 (hardback)
020 _z9780521117920 (paperback)
040 _aUkCbUP
_beng
_erda
_cUkCbUP
050 0 4 _aQA76.58
_b.D53 1997
082 0 0 _a511/.6/0285435
_221
100 1 _aDíaz, J.
_q(Josep),
_d1950-
_eauthor.
245 1 0 _aParadigms for fast parallel approximability /
_cJosep Díaz [and others].
264 1 _aCambridge :
_bCambridge University Press,
_c1997.
300 _a1 online resource (viii, 158 pages) :
_bdigital, PDF file(s).
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
490 1 _aCambridge international series on parallel computation ;
_v8
500 _aTitle from publisher's bibliographic system (viewed on 05 Oct 2015).
505 0 0 _tBasic concepts --
_tExtremal graph properties --
_tRounding, interval partitioning and separation --
_tPrimal-dual method --
_tGraph decomposition --
_tFurther parallel approximations --
_tNon-approximability --
_tSyntactically defined classes.
520 _aVarious problems in computer science are 'hard', that is NP-complete, and so not realistically computable; thus in order to solve them they have to be approximated. This book is a survey of the basic techniques for approximating combinatorial problems using parallel algorithms. Its core is a collection of techniques that can be used to provide parallel approximations for a wide range of problems (for example, flows, coverings, matchings, travelling salesman problems, graphs), but in order to make the book reasonably self-contained, the authors provide an introductory chapter containing the basic definitions and results. A final chapter deals with problems that cannot be approximated, and the book is ended by an appendix that gives a convenient summary of the problems described in the book. This is an up-to-date reference for research workers in the area of algorithms, but it can also be used for graduate courses in the subject.
650 0 _aParallel processing (Electronic computers)
776 0 8 _iPrint version:
_z9780521431705
830 0 _aCambridge international series on parallel computation ;
_v8.
856 4 0 _uhttps://doi.org/10.1017/CBO9780511666407
999 _c517384
_d517382