From nobody@cs.Buffalo.EDU Thu Jun 4 14:07 EDT 1998 From: nobody@cs.Buffalo.EDU Date: Thu, 4 Jun 1998 14:07:27 -0400 (EDT) To: techreps@cs.Buffalo.EDU Subject: techrep: POST request Content-Type: text Content-Length: 1349 Comments: I guess the file is on hadar. Thanks Davin! (the link to subject categories does not work!) ContactPerson: slavik@cs.buffalo.edu Remote host: alnilam.cedar.buffalo.edu Remote ident: slavik ### Begin Citation ### Do not delete this line ### %R 98-06 %U /u1/csgrad/slavik/Thesis/thesis.ps %A Slavik, Petr %T Approximation Algorithms for Set Cover and Related Problems %D April 30, 1998 %I Department of Computer Science, SUNY Buffalo %K Approximation Algorithms, Combinatorial Optimization, Errand Scheduling, Generalized Traveling Salesman Problem, Group Steiner Tree Problem, Partial Set Cover, Set Cover, Tree Cover Problem %X In this thesis, we analyze several known and newly designed algorithms for approximating optimal solutions to NP-hard optimization problems. We give a new analysis of the greedy algorithm for approximating the SET COVER and PARTIAL SET COVER problems obtaining significantly improved performance bounds. We also give a first approximation algorithm with a non-trivial performance bound for the ERRAND SCHEDULING and TREE COVER problems, known also as the GENERALIZED TRAVELING SALESMAN and GROUP STEINER TREE problems. The main results of this thesis first appeared in my papers [87], [89], [91], and [90]; and in my technical reports [86] and [88].