References

1

Aggarwal, A., Coppersmith, D., Khanna, S., Motwani, R., and Schieber, B. (1997), ``The angular-metric traveling salesman problem'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 221-229. (ND31)

2

Aggarwal, M., and Garg, N. (1994), ``A scaling technique for better network design'', Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 233-239. (ND9)

3

Akutsu, T., and Halldórsson, M. (1994), ``On the approximation of largest common point sets and largest common subtrees'', Proc. 5th Ann. Int. Symp. on Algorithms and Computation , Lecture Notes in Comput. Sci. 834, Springer-Verlag, 405-413. (SR7, SR8)

4

Alimonti, P., and Kann, V. (1997), ``Hardness of approximating problems on cubic graphs'', Proc. 3rd Italian Conf. on Algorithms and Complexity , Lecture Notes in Comput. Sci. 1203, Springer-Verlag, 288-298. (GT1, ND11)

5

Alon, N., Azar, Y., Woeginger, G. J., and Yadid, T. (1997), ``Approximation schemes for scheduling'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 493-500. (SS11)

6

Alon, N., Feige, U., Wigderson, A., and Zuckerman, D. (1995), ``Derandomized graph products'', Computational Complexity 5 , 60-75. (GT21)

7

Alon, N., and Kahale, N. (1994), ``Approximating the independence number via the -function'', Unpublished manuscript. (GT20)

8

Alon, N., Yuster, R., and Zwick, U. (1994), ``Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs'', Proc. 26th Ann. ACM Symp. on Theory of Comp. , ACM, 326-335. (ND39)

9

Amaldi, E., and Kann, V. (1994), ``On the approximability of removing the smallest number of relations from linear systems to achieve feasibility'', Technical Report ORWP-6-94, Department of Mathematics, Swiss Federal Institute of Technology, Lausanne, and Technical Report TRITA-NA-9402, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm. (MP9, MP11, MP12)

10

Amaldi, E., and Kann, V. (1995), ``The complexity and approximability of finding maximum feasible subsystems of linear relations'', Theoretical Computer Science 147 , 181-210. (MP10, MP12, AN1)

11

Anily, A., Bramel, J., and Simchi-Levi, D. (1994), ``Worst-case analysis of heuristics for the bin-packing problem with general cost structures'', Oper. Res. 42 , 287-298. (SR1)

12

Anily, S., and Hassin, R. (1992), ``The swapping problem'', Networks 22 , 419-433. (ND30)

13

Arkin, E. M., Chiang, Y., Mitchell, J. S. B., Skiena, S. S., and Yang, T. (1997), ``On the maximum scatter TSP'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 211-220. (ND33)

14

Arkin, E. M., Halldórsson, M. M., and Hassin, R. (1993), ``Approximating the tree and tour covers of a graph'', Inform. Process. Lett. 47 , 275-282. (GT1)

15

Arkin, E. M., and Hassin, R. (1992), ``Multiple-choice minimum diameter problems'', Unpublished manuscript. (SP4)

16

Arkin, E. M., and Hassin, R. (1993), ``Approximation algorithms for the geometric covering salesman problem'', Disc. Appl. Math. , to appear. (ND30)

17

Arkin, E.M., Hassin, R., and Klein, L. (1994), ``Restricted delivery problems on a network'', Unpublished manuscript. (ND30)

18

Armen, C., and Stein, C. (1994), ``A 2 -approximation algorithm for the shortest superstring problem'', Technical Report PCS-TR94-214, Department of Computer Science, Dartmouth College, Hanover, New Hampshire. (SR5)

19

Arora, S. (1996), ``Polynomial time approximation scheme for euclidean TSP and other geometric problems'', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 2-11. (ND1, ND3, ND7, ND31)

20

Arora, S. (1997), ``Nearly linear time approximation schemes for Euclidean TSP and other geometric problems'', Unpublished manuscript. (ND7, ND31)

21

Arora, S., Babai, L., Stern, J., and Sweedyk, Z. (1993), ``The hardness of approximate optima in lattices, codes, and systems of linear equation'', Proc. 34th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 724-733. (MP11, MP16, MS2)

22

Arora, S., Babai, L., Stern, J., and Sweedyk, Z. (1994), ``The hardness of approximate optima in lattices, codes, and systems of linear equation'', Unpublished manuscript. (MP11, MP12, MP16, MS2)

23

Arora, S., Frieze, A., and Kaplan, H. (1996), ``A new rounding procedure for the assignment problem with applications to dense graph arrangement problems'', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 21-30. (GT9, GT40, GT41, MS1)

24

Arora, S., Karger, D., and Karpinski, M. (1995), ``Polynomial time approximation schemes for dense instances of NP-hard problems'', Proc. 27th Ann. ACM Symp. on Theory of Comp. , ACM, 284-293. (GT31, GT32, ND11, ND13, ND16, ND18, ND21, SP3, LO2)

25

Aumann, Y., and Rabani, Y. (1995), ``Improved bounds for all optical routing'', Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 567-576. (ND44)

26

Aumann, Y., and Rabani, Y. (1996), ``An approximate min-cut max-flow theorem and approximation algorithm'', SIAM J. Comp. , to appear. (ND20)

27

Ausiello, G., D'Atri, A., and Protasi, M. (1980), ``Structure preserving reductions among convex optimization problems'', J. Comput. System Sci. 21 , 136-153. (GT8, SP2, SP4, SP7)

28

Ausiello, G., D'Atri, A., and Protasi, M. (1981), ``Lattice theoretic ordering properties for NP-complete optimization problems'', Annales Societatis Mathematicae Polonae 4 , 83-94. (LO6)

29

Awerbuch, B., Azar, Y., Blum, A., and Vempala, S. (1995), ``Improved approximation guarantees for minimum-weight k -trees and prize-collecting salesmen'', Proc. 27th Ann. ACM Symp. on Theory of Comp. , ACM, 277-283. (ND7)

30

Bafna, V., Berman, P., and Fujito, T. (1994), ``Approximating feedback vertex set for undirected graphs within ratio 2'', Unpublished manuscript. (GT8)

31

Bafna, V., and Pevzner, P. A. (1993), ``Genome rearrangements and sorting by reversals'', Proc. 34th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 148-157. (MS9)

32

Bafna, V., and Pevzner, P. A. (1995), ``Sorting permutations by transpositions'', Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 614-621. (MS9)

33

Baker, B. S. (1994), ``Approximation algorithms for NP-complete problems on planar graphs'', J. ACM 41 , 153-180. (GT1, GT2, GT3, GT10, GT11, GT21)

34

Bandelt, H., Crama, Y., and Spieksma, F. C. R. (1991), ``Approximation algorithms for multidimensional assignment problems with decomposable costs'', Technical Report RRR 33-91, Rutgers Center for Operations Research. (SP10)

35

Bar-Ilan, J., Kortsarz, G., and Peleg, D. (1996), ``Generalized submodular cover problems and applications'', Proc. 4th Israel Symp. on Theory of Computing and Systems , IEEE Computer Society, 110-118. (ND7)

36

Bar-Ilan, J., and Peleg, D. (1991), ``Approximation algorithms for selecting network centers'', Algorithms and Data structures , Lecture Notes in Comput. Sci. 519, Springer-Verlag, 343-354. (ND48)

37

Bar-Yehuda, R., and Even, S. (1985), ``A local-ratio theorem for approximating the weighted vertex cover problem'', in Analysis and Design of Algorithms for Combinatorial Problems , volume 25 of Annals of Disc. Math. , , Annals of Disc. Math., Elsevier science publishing company, Amsterdam, 27-46. (GT1)

38

Barvinok, A. I. (1996), ``Two algorithmic results for the traveling salesman problem'', Math. Oper. Res. 21 , 65-84. (ND31)

39

Bellare, M. (1993), ``Interactive proofs and approximation: reductions from two provers in one round'', Proc. 2nd Israel Symp. on Theory of Computing and Systems , IEEE Computer Society, 266-274. (ND39, ND42, SP11)

40

Bellare, M., Goldreich, O., and Sudan, M. (1995), ``Free bits, PCPs and non-approximability - towards tight results'', Proc. 36th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 422-431. (GT5, GT20, SR6, MS10)

41

Bellare, M., Goldwasser, S., Lund, C., and Russell, A. (1993), ``Efficient probabilistically checkable proofs and applications to approximation'', Proc. 25th Ann. ACM Symp. on Theory of Comp. , ACM, 294-304. (GT2, SP4)

42

Bellare, M., and Rogaway, P. (1995), ``The complexity of approximating a nonlinear program'', in , volume 69, , , 429-441. (MP5)

43

Berger, B., and Cowen, L. (1991), ``Complexity results and algorithms for -constrained scheduling'', Proc. Second Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 137-147. (SS7)

44

Berger, B., and Shor, P. W. (1990), ``Approximation algorithms for the maximum acyclic subgraph problem'', Proc. First Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 236-243. (GT9)

45

Berman, F., Johnson, D., Leighton, T., Shor, P. W., and Snyder, L. (1990), ``Generalized planar matching'', J. Algorithms 11 , 153-184. (GT11)

46

Berman, P., and Fujito, T. (1995), ``Approximating independent sets in degree 3 graphs'', Proc. 4th Workshop on Algorithms and Data Structures , Lecture Notes in Comput. Sci. 955, Springer-Verlag, 449-460. (GT1, GT21, SP2)

47

Berman, P., and Fürer, M. (1994), ``Approximating maximum independent set in bounded degree graphs'', Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 365-371. (GT21)

48

Berman, P., and Ramaiyer, V. (1994), ``Improved approximations for the Steiner tree problem'', J. Algorithms 17 , 381-408. (ND8)

49

Berman, P., and Schnitger, G. (1992), ``On the complexity of approximating the independent set problem'', Inform. and Comput. 96 , 77-94. (GT26, GT46, SR6, MP2, LO12, AL2)

50

Bern, M., and Plassmann, P. (1989), ``The Steiner problem with edge lengths 1 and 2'', Inform. Process. Lett. 32 , 171-176. (ND7)

51

Bernstein, D., Rodeh, M., and Gertner, I. (1989), ``Approximation algorithms for scheduling arithmetic expressions on pipelined machines'', J. Algorithms 10 , 120-139. (SS3)

52

Bertsimas, D., Teo, C-P., and Vohra, R. (1996), ``On dependent randomized rounding algorithms'', Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization , Lecture Notes in Comput. Sci. 1084, Springer-Verlag, 330-344. (GT7, LO1, LO3)

53

Blaha, K. D. (1992), ``Minimum bases for permutation groups: the greedy approximation'', J. Algorithms 13 , 297-306. (AL5)

54

Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., and Sudan, M. (1994), ``The minimum latency problem'', Proc. 26th Ann. ACM Symp. on Theory of Comp. , ACM, 163-171. (ND30)

55

Blum, A., Jiang, T., Li, M., Tromp, J., and Yannakakis, M. (1994), ``Linear approximation of shortest superstrings'', J. ACM 41 , 630-647. (SR5)

56

Blundo, C., De Santis, A., and Vaccaro, U. (1994), ``Randomness in distribution protocols'', Unpublished manuscript. (GT22)

57

Bodlaender, H. L., Gilbert, J. R., Hafsteinsson, H., and Kloks, T. (1995), ``Approximating treewidth, pathwidth, frontsize and shortest elimination tree'', J. Algorithms 18 , 238-255. (GT50)

58

Bonizzoni, P., Duella, M., and Mauri, G. (1994), ``Approximation complexity of longest common subsequence and shortest common supersequence over fixed alphabet'', Technical Report 117/94, Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano. (SR4, SR6)

59

Boppana, R., and Halldórsson, M. M. (1992), ``Approximating maximum independent sets by excluding subgraphs'', Bit 32 , 180-196. (GT20)

60

Bui, T. N., and Jones, C. (1992), ``Finding good approximate vertex and edge partitions is NP-hard'', Inform. Process. Lett. 42 , 153-159. (ND21, ND22)

61

Calinescu, G., Fernandes, C. G., Finkler, U., and Karloff, H. (1996), ``A better approximation algorithm for finding planar subgraphs'', Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 16-25. (GT29)

62

Chakrabati, S., Phillips, C. A., Schulz, A. S., Shmoys, D. B., Stein, C., and Wein, J. (1996), ``Improved scheduling algorithms for minsum criteria'', Proc. 23rd Int. Colloquium on Automata, Languages and Programming , Lecture Notes in Comput. Sci. 1099, Springer-Verlag, 646-657. (SS12)

63

Chandra, A. K., Hirschberg, D. S., and Wong, C. K. (1976), ``Approximate algorithms for some generalized knapsack problems'', Theoretical Computer Science 3 , 293-304. (MP14, MP15)

64

Chaudhary, A., and Vishwanathan, S. (1997), ``Approximation algorithms for the achromatic number'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 558-563. (GT6)

65

Chekuri, C., Motwani, R., Natarajan, B., and Stein, C. (1997), ``Approximation techniques for average completion time scheduling'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 609-618. (SS4, SS12)

66

Chen, B. (1993), ``A better heuristic for preemptive parallel machine scheduling with batch setup times'', SIAM J. Comp. 22 , 1303-1318. (SS9)

67

Chen, B. (1994), ``Scheduling multiprocessor flow shops'', in Advances in Optimization and Approximation , Kluwer Academic Publishers, The Netherlands, 1-8. (SS15)

68

Chen, B., Glass, C. A., Potts, C. N., and Strusevich, V. A. (1995), ``A new heuristic for three-machine flow shop scheduling'', Oper. Res. , to appear. (SS15)

69

Chen, B., Potts, C. N., and Strusevich, V. A. (1995), ``Approximation algorithms for two-machine flow shop scheduling with batch setup times'', Technical Report 152, Warwick Business School Research Paper, University of Warwick. (SS16)

70

Chen, B., and Strusevich, V. A. (1993a), ``Approximation algorithms for three-machine open shop scheduling'', ORSA J. Comput. 5 , 321-326. (SS14)

71

Chen, B., and Strusevich, V. A. (1993b), ``Worst-case analysis of heuristics for open shops with parallel machines'', European J. Oper. Res. 70 , 379-390. (SS14)

72

Cheriyan, J., and Thurimella, R. (1996), ``Approximating minimum-size k -connected spanning subgraps via matching'', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 292-301. (ND24, ND25)

73

Choi, J., Sellen, J., and Yap, C. K. (1994), ``Approximate Euclidean shortest path motion planning'', Proc. 10th Ann. ACM Symp. Comput. Geom. , ACM, . (MS11)

74

Chor, B., and Sudan, M. (1995), ``A geometric approach to betweenness'', Proc. 3rd Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 979, Springer-Verlag, 227-237. (MS1)

75

Christofides, N. (1976), ``Worst-case analysis of a new heuristic for the travelling salesman problem'', Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh. (ND30)

76

Chudak, F. A., and Shmoys, D. B. (1997), ``Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speed'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 581-590. (SS7)

77

Chvátal, V. (1979), ``A greedy heuristic for the set covering problem'', Math. Oper. Res. 4 , 233-235. (SP4)

78

Clementi, A., and Ianni, M. Di (1996), ``On the hardness of approximating optimum schedule problems in store and forward networks'', IEEE/ACM Transaction on Networking 4 , 272-280. (SS19)

79

Clementi, A., and Trevisan, L. (1996), ``Improved non-approximability results for vertex cover problems with density constraints'', Proc. 2nd Ann. Int. Conf. on Computing and Combinatorics , Lecture Notes in Comput. Sci. 1090, Springer-Verlag, 333-342. (GT1)

80

Coffman, E. G., Garey, M. R., Johnson, D. S., and Lapaugh, A. S. (1985), ``Scheduling file transfers'', SIAM J. Comp. 14 , 744-780. (SS18)

81

Coffman, E. G., Jr, Garey, M. R., and Johnson, D. S. (1984), ``Approximation algorithms for bin-packing - an updated survey'', in Algorithm Design for Computer System Design , Springer-Verlag, New York, 49-106. (SR1)

82

Cornuejols, G., Fisher, M., and Nemhauser, G. (1977), ``Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms'', Management Sci. 23 , 789-810. (ND55)

83

Cowen, L. J., Goddard, W., and Jesurum, C. E. (1997), ``Coloring with defect'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 548-557. (GT5)

84

Crama, Y., and Spieksma, F. C. R. (1992), ``Approximation algorithms for three-dimensional assignment problems with triangle inequalities'', European J. Oper. Res. 60 , 273-279. (SP10)

85

Crescenzi, P., Kann, V., Silvestri, R., and Trevisan, L. (1995), ``Structure in approximation classes'', Proc. 1st Ann. Int. Conf. on Computing and Combinatorics , Lecture Notes in Comput. Sci. 959, Springer-Verlag, 539-548. (GT7, ND2, SR1)

86

Crescenzi, P., and Panconesi, A. (1991), ``Completeness in approximation classes'', Inform. and Comput. 93 , 241-262. (LO8)

87

Crescenzi, P., Silvestri, R., and Trevisan, L. (1994), ``On the query complexity of complete problems in approximation classes'', Unpublished manuscript.

88

Crescenzi, P., and Trevisan, L. (1994), ``On approximation scheme preserving reducibility and its applications'', Proc. 14th Ann. Conf. on Foundations of Software Tech. and Theoret. Comput. Sci. , Lecture Notes in Comput. Sci. 880, Springer-Verlag, 330-341.

89

Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., and Yannakakis, M. (1994), ``The complexity of multiterminal cuts'', SIAM J. Comp. 23 , 864-894. (ND18)

90

d¹Anzeo, C. (1996), ``Optimization complexity of the scs problem given a longest common subsequence'', Unpublished manuscript. (SR4)

91

DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., and Zhang, L. (1997), ``On distances between phylogenetic trees'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 427-436. (MS13)

92

Datta, A. K., and Sen, R. K. (1995), ``1-approximation algorithm for bottleneck disjoint path matching'', Inform. Process. Lett. 55 , 41-44. (GT12)

93

Doddi, S., Marathe, M. V., Mirzaian, A., Moret, B. M. E., and Zhu, B. (1997), ``Map labeling and its generalizations'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 148-157. (MS12)

94

Dudek, G., Romanik, K., and Whitesides, S. (1994), ``Localizing a robot with minimum travel'', Technical Report SOCS-94.5, McGill University. (GP2)

95

Eades, P., and Wormald, N. C. (1994), ``Edge crossings in drawings of bipartite graphs'', Algorithmica 11 , 379-403. (ND12)

96

Eppstein, D. (1992), ``Approximating the minimum weight triangulation'', Proc. Third Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 48-57. (ND58)

97

Errico, B., and Rosati, R. (1995), ``Minimal models in propositional logics: approximation results'', Proc. of 5th Italian Conference on Theoretical Computer Science , Word Scientific, 547-562. (LO7)

98

Even, G., Naor, J., Rao, S., and Schieber, B. (1997), ``Fast approximate graph partitioning algorithms'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 639-648. (ND21)

99

Even, G., Naor, J., Schieber, B., and Sudan, M. (1995), ``Approximating minimum feedback sets and multi-cuts in directed graphs'', Proc. 4th Int. Conf. on Integer Prog. and Combinatorial Optimization , Lecture Notes in Comput. Sci. 920, Springer-Verlag, 14-28. (GT8, GT9)

100

Even, G., Naor, J., and Zosin, L. (1996), ``An 8-approximation algorithm for the subset feedback vertex set problem'', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 310-319. (GT8)

101

Farach, M., Kannan, S., and Warnow, T. (1993), ``A robust model for finding optimal evolutionary trees'', Proc. 25th Ann. ACM Symp. on Theory of Comp. , ACM, 137-145. (MS7)

102

Feder, T., and Greene, D. H. (1988), ``Optimal algorithms for approximate clustering'', Proc. 20th Ann. ACM Symp. on Theory of Comp. , ACM, 434-444. (ND33, ND48, ND49)

103

Feige, U. (1996), ``A threshold of for approximating set cover'', Proc. 28th Ann. ACM Symp. on Theory of Comp. , ACM, 314-318. (GT2, SP4)

104

Feige, U., and Goemans, M. X. (1995), ``Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT'', Proc. 3rd Israel Symp. on Theory of Computing and Systems , IEEE Computer Society, 182-189. (ND13, LO2)

105

Feige, U., and Kilian, J. (1996), ``Zero knowledge and the chromatic number'', Proc. Comp. Complexity , , . (GT5)

106

Feige, U., Kortsarz, G., and Peleg, D. (1995), ``The dense k -subgraph problem'', Unpublished manuscript. (GT32)

107

Fernandes, C. G. (1997), ``A better approximation ratio for the minimum k -edge-connected spanning subgraph problem'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 629-638. (ND25)

108

Fernandez de la Vega, W., and Zissimopoulos, V. (1991), ``An approximation scheme for strip-packing of rectangles with bounded dimensions'', Technical Report 713, Laboratoire de Recherche en Informatique, Université de Paris, Orsay. (SR2)

109

Floréen, P., and Orponen, P. (1993), ``Attraction radii in binary Hopfield nets are hard to compute'', Neural Comput. 5 , 812-821. (MS4)

110

Formann, M., and Wagner, F. (1991), ``A packing problem with applications to lettering of maps'', Proc. 7th Annual ACM Symposium on Computational Geometry , ACM, 281-288. (MS12)

111

Frederickson, G. N. (1979), ``Approximation algorithms for some postman problems'', J. ACM 26 , 538-554. (ND34)

112

Frederickson, G. N., Hecht, M. S., and Kim, C. E. (1978), ``Approximation algorithms for some routing problems'', SIAM J. Comp. 7 , 178-193. (ND32, ND35, ND36, ND37)

113

Frederickson, G. N., and Jájá, J. (1981), ``Approximation algorithms for several graph augmentation problems'', SIAM J. Comp. 10 , 270-283. (ND26, ND27)

114

Frederickson, G. N., and Jájá, J. (1982), ``On the relationship between the biconnectivity augmentation and traveling salesman problems'', Theoretical Computer Science 19 , 189-201. (ND24, ND26)

115

Frieze, A., Galbiati, G., and Maffioli, F. (1982), ``On the worst-case performance of some algorithms for the asymmetric traveling salesman problem'', Networks 12 , 23-39. (ND30)

116

Frieze, A., and Jerrum, M. (1995), ``Improved approximation algorithms for MAX k -CUT and MAX BISECTION'', Proc. 4th Int. Conf. on Integer Prog. and Combinatorial Optimization , Lecture Notes in Comput. Sci. 920, Springer-Verlag, 1-13. (GT31, ND11, ND14)

117

Fürer, M., and Raghavachari, B. (1994), ``Approximating the minimum-degree Steiner tree to within one of optimal'', J. Algorithms 17 , 409-423. (ND2)

118

Galbiati, G., Maffioli, F., and Morzenti, A. (1994), ``A short note on the approximability of the maximum leaves spanning tree problem'', Inform. Process. Lett. 52 , 45-49. (ND4)

119

Galbiati, G., Maffioli, F., and Morzenti, A. (1995), ``On the approximability of some maximum spanning tree problems'', Proc. 2nd Int. Symp. Latin American Theoretical Informatics , Lecture Notes in Comput. Sci. 911, Springer-Verlag, 300-311. (ND4)

120

Garey, M., and Graham, R. (1975), ``Bounds for multiprocessor scheduling with resource constraints'', SIAM J. Comp. 4 , 187-200. (SS8)

121

Garey, M. R., and Johnson, D. S. (1979), Computers and Intractability: a guide to the theory of NP-completeness , W. H. Freeman and Company, San Francisco. (ND2, SR1)

122

Garg, A., and Tamassia, R. (1994), ``On the computational complexity of upward and rectilinear planarity testing'', Proc. DIMACS Int. Workshop on Graph Drawing , Lecture Notes in Comput. Sci. 894, Springer-Verlag, 286-297. (ND57)

123

Garg, N. (1996), ``A 3-approximation for the minimum tree spanning k vertices'', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 302-309. (ND1)

124

Garg, N., Santosh, V. S., and Singla, A. (1993), ``Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques'', Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 103-111. (ND24)

125

Garg, N., Saran, H., and Vazirani, V. (1994), ``Finding separator cuts in planar graphs within twice the optimal'', Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 14-23. (ND21)

126

Garg, N., Vazirani, V. V., and Yannakakis, M. (1993), ``Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover'', Proc. 20th Int. Colloquium on Automata, Languages and Programming , Lecture Notes in Comput. Sci. 700, Springer-Verlag, 64-75. (ND19, ND43, SP4)

127

Garg, N., Vazirani, V. V., and Yannakakis, M. (1994), ``Multiway cuts in directed and node weighted graphs'', Proc. 21st Int. Colloquium on Automata, Languages and Programming , Lecture Notes in Comput. Sci. 820, Springer-Verlag, 487-498. (GT24, ND17, ND18, ND19)

128

Garg, N., Vazirani, V. V., and Yannakakis, M. (1996), ``Approximate max-flow min-(multi)cut theorems and their applications'', SIAM J. Comp. 25 , 235-251. (GT30, ND19, LO11)

129

Gens, G. V., and Levner, E. V. (1979), ``Computational complexity of approximation algorithms for combinatorial problems'', Proc. 8th International Symp. on Mathematical Foundations of Comput. Sci. , Lecture Notes in Comput. Sci. 74, Springer-Verlag, 292-300. (MP13, MP15)

130

Gil, J., and Itai, A. (1995), ``Packing trees'', Proc. 3rd Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 979, Springer-Verlag, 113-127. (SR10)

131

Goemans, M. X. (1994), ``An approximation algorithm for scheduling on three dedicated machines'', Disc. Appl. Math. , to appear. (SS13)

132

Goemans, M. X. (1997), ``Improved approximation algorithms for scheduling with release dates'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 591-598. (SS4)

133

Goemans, M. X., Goldberg, A. V., Plotkin, S., Shmoys, D. B., Tardos, É., and Williamson, D. P. (1994), ``Improved approximation algorithms for network design problems'', Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 223-232. (ND9)

134

Goemans, M. X., and Williamson, D. P. (1995a), ``A general approximation technique for constrained forest problems'', SIAM J. Comp. 24 , 296-317. (GT14, GT48, ND7, ND30)

135

Goemans, M. X., and Williamson, D. P. (1995b), ``Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming'', J. ACM 42 , 1115-1145. (ND11, LO1)

136

Goemans, M. X., and Williamson, D. P. (1996), ``Primal-dual approximation algorithms for feedback problems in planar graphs'', Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization , Lecture Notes in Comput. Sci. 1084, Springer-Verlag, 147-161. (GT8, GT9, GT30)

137

Goldberg, L. A., Paterson, M., Srinivasan, A., and Sweedyk, E. (1997), ``Better approximation guarantees for job-shop scheduling'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 599-608. (SS17)

138

Goldschmidt, O., and Hochbaum, D. S. (1988), ``Polynomial algorithm for the k -cut problem'', Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 444-451. (ND16)

139

Gonzalez, T. F. (1985), ``Clustering to minimize the maximum intercluster distance'', Theoretical Computer Science 38 , 293-306. (ND49)

140

Gonzalez, T. F., and Zheng, S. (1989), ``Improved bounds for rectangular and Guilhotine partitions'', J. Symbolic Comput. 7 , 591-610. (MS8)

141

Gonzalez, T. F., and Zheng, S. (1990), ``Approximation algorithm for partitioning a rectangle with interior points'', Algorithmica 5 , 11-42. (MS8)

142

Grigoriadis, M. D., and Khachiyan, L. G. (1994), ``Fast approximation schemes for convex programs with many blocks and coupling constraints'', SIAM J. Optimization 4 , 86-107. (MP17)

143

Guha, S., and Khuller, S. (1996), ``Approximation algorithms for connected dominating sets'', Proc. 4th Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 1136, Springer-Verlag, 179-193. (GT2)

144

Gusfield, D., and Pitt, L. (1992), ``A bounded approximation for the minimum cost 2-sat problem'', Algorithmica 8 , 103-117. (LO7)

145

Guttman, N., and Hassin, R. (1996), ``Approximation algorithms for minimum sum p -checking'', Unpublished manuscript. (ND50)

146

Hall, L. A., Schulz, A. S., Shmoys, D. B., and Wein, J. (1997), ``On-line and off-line approximation algorithms'', Unpublished manuscript. (SS4)

147

Hall, N. G., and Hochbaum, D. S. (1986), ``A fast approximation algorithm for the multicovering problem'', Disc. Appl. Math. 15 , 35-40. (MP1)

148

Halldórsson, M. M. (1993a), ``A still better performance guarantee for approximate graph coloring'', Inform. Process. Lett. 45 , 19-23. (GT5, GT13)

149

Halldórsson, M. M. (1993b), ``Approximating the minimum maximal independence number'', Inform. Process. Lett. 46 , 169-172. (GT4)

150

Halldórsson, M. M. (1994), ``personal communication'', Unpublished manuscript. (GT15, GT16, GT34, GT42, SP1)

151

Halldórsson, M. M. (1995a), ``Approximating discrete collections via local improvements'', Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 160-169. (GT1, GT21, GT34)

152

Halldórsson, M. M. (1995b), ``Approximation via partitioning'', Technical Report IS-RR-95-0003F, School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku. (GT20, GT21, GT22, GT23, SR6, MP10)

153

Halldórsson, M. M. (1996), ``Approximating k -set cover and complementary graph coloring'', Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization , Lecture Notes in Comput. Sci. 1084, Springer-Verlag, 118-131. (GT5, GT13, GT15, SP4)

154

Halldórsson, M. M., Iwano, K., Katoh, N., and Tokuyama, T. (1995), ``Finding subsets maximizing minimum structures'', Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 150-159. (ND5)

155

Halldórsson, M. M., and Radhakrishnan, J. (1994), ``Improved approximations of independent sets in bounded-degree graphs'', Nordic J. Comp. 1 , 475-492. (GT21)

156

Halldórsson, M. M., and Tanaka, K. (1996), ``Approximation and special cases of common subtrees and editing distance'', Proc. 7th Ann. Int. Symp. on Algorithms and Computation , Lecture Notes in Comput. Sci. 1178, , 75-84. (GT44)

157

Halldórsson, M. M., Ueno, S., Nakao, H., and Kajitani, Y. (1992), ``Approximating Steiner trees in graphs with restricted weights'', Proc. Asia-Pacific Conference on Circuits and Systems, Sidney, Australia , , 69-73. (ND7)

158

Haralambides, J., Makedon, F., and Monien, B. (1991), ``Bandwidth minimization: an approximation algorithm for caterpillars'', Math. Systems Theory 24 , 169-177. (GT39)

159

Hassin, R. (1992), ``Approximation schemes for the restricted shortest path problem'', Math. Oper. Res. 17 , 36-42. (ND40)

160

Hassin, R., and Megiddo, N. (1991), ``Approximation algorithms for hitting objects with straight lines'', Disc. Appl. Math. 30 , 29-42. (SP7)

161

Hassin, R., and Rubinstein, S. (1994), ``Approximations for the maximum acyclic subgraph problem'', Inform. Process. Lett. 51 , 133-140. (GT9)

162

Hassin, R., Rubinstein, S., and Tamir, A. (1994), ``Notes on dispersion problems'', Unpublished manuscript. (GT32)

163

Håstad, J. (1996), ``Clique is hard to approximate within '', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 627-636. (GT20)

164

Håstad, J. (1997), ``Some optimal inapproximability results'', Proc. 29th Ann. ACM Symp. on Theory of Comp. , ACM, to appear. (GT1, GT30, ND11, ND13, MP10, LO2)

165

Håstad, J., Phillips, S., and Safra, S. (1993), ``A well-characterized approximation problem'', Inform. Process. Lett. 47 , 301-305. (AN1)

166

Hochbaum, D. S. (1982), ``Approximation algorithms for the set covering and vertex cover problems'', SIAM J. Comp. 11 , 555-556. (GT1, SP4)

167

Hochbaum, D. S. (1983), ``Efficient bounds for the stable set, vertex cover and set packing problems'', Disc. Appl. Math. 6 , 243-254. (GT21, SP2)

168

Hochbaum, D. S. (1997), ``Various notions of approximations: good, better, best, and more'', in Approximation algorithms for NP-hard problems , PWS Publishing Company, Boston, 346-398. (ND48)

169

Hochbaum, D. S., and Maass, W. (1985), ``Approximation schemes for covering and packing problems in image processing and VLSI'', J. ACM 32 , 130-136. (SP8)

170

Hochbaum, D. S., and Maass, W. (1987), ``Fast approximation algorithms for a nonconvex covering problem'', J. Algorithms 8 , 305-323. (SP8)

171

Hochbaum, D. S., Megiddo, N., Naor, J., and Tamir, A. (1993), ``Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality'', Math. Programming 62 , 69-83. (MP1)

172

Hochbaum, D. S., and Shmoys, D. B. (1986), ``A unified approach to approximation algorithms for bottleneck problems'', J. ACM 33 , 533-550. (ND33, ND48, ND49, ND51, ND56)

173

Hochbaum, D. S., and Shmoys, D. B. (1987), ``Using dual approximation algorithms for scheduling problems: theoretical and practical results'', J. ACM 34 , 144-162. (SS6)

174

Hochbaum, D. S., and Shmoys, D. B. (1988), ``A polynomial approximation scheme for machine scheduling on uniform processors: using the dual approach'', SIAM J. Comp. 17 , 539-551. (SS10)

175

Holyer, I. (1981), ``The NP-completeness of edge-coloring'', SIAM J. Comp. 10 , 718-720. (GT7)

176

Hoogeveen, J. A., Lenstra, J. K., and Veltman, B. (1995), ``Three, four, five, six, or the complexity of scheduling with communication delays'', Oper. Res. Lett. to appear , . (SS7)

177

Horowitz, E., and Sahni, S. (1978), Fundamentals of computer algorithms , Pitman, . (GT5)

178

Horowitz, E., and Sahni, S. K. (1976), ``Exact and approximate algorithms for scheduling nonidentical processors'', J. ACM 23 , 317-327. (SS6, SS10)

179

Hsu, W. L., and Nemhauser, G. L. (1979), ``Easy and hard bottleneck location problems'', Disc. Appl. Math. 1 , 209-216. (ND48)

180

Hunt III, H. B., Marathe, M. V., Radhakrishnan, V., Ravi, S. S., Rosenkrantz, D. J., and Stearns, R. E. (1994a), ``Approximation schemes using L-reductions'', Proc. 14th Ann. Conf. on Foundations of Software Tech. and Theoret. Comput. Sci. , Lecture Notes in Comput. Sci. 880, Springer-Verlag, 342-353. (GT34)

181

Hunt III, H. B., Marathe, M. V., Radhakrishnan, V., Ravi, S. S., Rosenkrantz, D. J., and Stearns, R. E. (1994b), ``A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs'', Proc. 2nd Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 855, Springer-Verlag, 424-435. (GT1, GT2, GT3, GT10, GT11, GT21)

182

Hurkens, C. A. J., and Schrijver, A. (1989), ``On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems'', SIAM J. Disc. Math. 2 , 68-72. (GT10, GT11, SP1, SP2)

183

Ianni, M. Di (1996), ``Efficient delay routing'', 2nd International EURO-PAR Conference , , Lecture Notes in Comput. Sci., Springer-Verlag, . (SS19)

184

Ibarra, O. H., and Kim, C. E. (1975), ``Fast approximation for the knapsack and sum of subset problems'', J. ACM 22 , 463-468. (MP13)

185

Ihler, E. (1991), ``Bounds on the quality of approximate solutions to the group Steiner problem'', Proc. 17th Workshop on Graph-Theoretic Concepts in Computer Science , Lecture Notes in Comput. Sci. 484, Springer-Verlag, 109-118. (ND7, ND8)

186

Ihler, E. (1992), ``The complexity of approximating the class Steiner tree problem'', Proc. 18th Workshop on Graph-Theoretic Concepts in Computer Science , Lecture Notes in Comput. Sci. 570, Springer-Verlag, 85-96. (ND7)

187

Jagota, A. (1993), ``Constraint satisfaction and maximum clique'', Working Notes, AAAI Spring Symposium on AI and NP-hard Problems , Stanford University, 92-97. (MS10)

188

Jansen, K. (1992), ``An approximation algorithm for the general routing problem'', Inform. Process. Lett. 41 , 333-339. (ND38)

189

Jansen, K., and Öhring, S. (1997), ``Approximation algorithms for time constrained scheduling'', Inform. and Comput. 132 , 85-108. (SR1)

190

Jiang, T., Lawler, E. L., and Wang, L. (1994), ``Aligning sequences via an evolutionary tree: complexity and approximation'', Proc. 26th Ann. ACM Symp. on Theory of Comp. , ACM, 760-769. (ND7, MS3)

191

Jiang, T., and Li, M. (1994a), ``Approximating shortest superstrings with constraints'', Theoretical Computer Science 134 , 473-491. (SR5)

192

Jiang, T., and Li, M. (1994b), ``On the approximation of shortest common supersequences and longest common subsequences'', Proc. 21st Int. Colloquium on Automata, Languages and Programming , Lecture Notes in Comput. Sci. 820, Springer-Verlag, 191-202. (SR4, SR6)

193

Jiang, T., and Wang, L. (1994), ``An approximation scheme for some Steiner tree problems in the plane'', Proc. 5th Ann. Int. Symp. on Algorithms and Computation , Lecture Notes in Comput. Sci. 834, Springer-Verlag, 414-422. (ND8)

194

Johnson, D. S. (1974), ``Approximation algorithms for combinatorial problems'', J. Comput. System Sci. 9 , 256-278. (GT2, SP4, SP5, LO2)

195

Johnson, D. S. (1990), ``A catalog of complexity classes'', in Algorithms and Complexity , volume A of Handbook of Theoretical Computer Science , , Handbook of Theoretical Computer Science, Elsevier science publishing company, Amsterdam, 67-161.

196

Johnson, D. S., and Garey, M. R. (1985), ``A 71/60 theorem for bin-packing'', J. Complexity 1 , 65-106. (SR1)

197

Jonsson, P. (1997), ``Tight lower bounds on the approximability of some NPO PB-complete problems'', Technical Report 4, Department of Computer and Information Science, Linköping University, Sweden. (MP2, LO6, LO7)

198

Kann, V. (1991), ``Maximum bounded 3-dimensional matching is MAX SNP-complete'', Inform. Process. Lett. 37 , 27-35. (GT10, SP1, SP2)

199

Kann, V. (1992a), ``On the approximability of the maximum common subgraph problem'', Proc. 9th Ann. Symp. on Theoretical Aspects of Comput. Sci. , Lecture Notes in Comput. Sci. 577, Springer-Verlag, 377-388. (GT42, GT43)

200

Kann, V. (1992b), On the Approximability of NP-complete Optimization Problems , PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm. (GT2, GT4, GT8, GT9, GT42, SP6, LO6, LO9)

201

Kann, V. (1994a), ``Maximum bounded H-matching is MAX SNP-complete'', Inform. Process. Lett. 49 , 309-318. (GT11)

202

Kann, V. (1994b), ``Polynomially bounded minimization problems that are hard to approximate'', Nordic J. Comp. 1 , 317-331. (GT4, GT47, MP1, LO7, LO10, AL3)

203

Kann, V. (1995), ``Strong lower bounds on the approximability of some NPO PB-complete maximization problems'', Proc. 20th International Symp. on Mathematical Foundations of Comput. Sci. , Lecture Notes in Comput. Sci. 969, Springer-Verlag, 227-236. (GT26, MP2, MP9)

204

Kann, V., Khanna, S., Lagergren, J., and Panconesi, A. (1997), ``Hardness of approximating MAX k -CUT and its dual'', Chicago Journal of Theoretical Computer Science , . (GT30, ND14)

205

Kann, V., Lagergren, J., and Panconesi, A. (1996), ``Approximability of maximum splitting of k -sets and some other APX-complete problems'', Inform. Process. Lett. 58 , 105-110. (SP3, LO4)

206

Karger, D., Motwani, R., and Ramkumar, G. D. S. (1993), ``On approximating the longest path in a graph'', Proc. 3rd Workshop on Algorithms and Data Structures , Lecture Notes in Comput. Sci. 709, Springer-Verlag, 421-432. (ND39)

207

Karger, D., Motwani, R., and Sudan, M. (1994), ``Approximate graph coloring by semidefinite programming'', Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 2-13. (GT5)

208

Karmarkar, N., and Karp, R. M. (1982), ``An efficient approximation scheme for the one-dimensional bin packing problem'', Proc. 23rd Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 312-320. (SR1)

209

Karp, R. M., McKellar, A. C., and Wong, C. K. (1975), ``Near-optimal solutions to a 2-dimensional placement problem'', SIAM J. Comp. 4 , 271-286. (MP8)

210

Karpinski, M., and Zelikovsky, A. (1995), ``New approximation algorithms for the Steiner tree problems'', Technical Report TR95-030, Electronic Colloquium on Computational Complexity. (ND7, ND8)

211

Karuno, Y., Nagamochi, H., and Ibaraki, T. (1993), ``Vehicle scheduling on a tree with release and handling times'', Proc. 4th Ann. Int. Symp. on Algorithms and Computation , Lecture Notes in Comput. Sci. 762, Springer-Verlag, 486-495. (SS20)

212

Kavvadias, D., Papadimitriou, C. H., and Sideri, M. (1993), ``On Horn envelopes and hypergraph transversals'', Proc. 4th Ann. Int. Symp. on Algorithms and Computation , Lecture Notes in Comput. Sci. 762, Springer-Verlag, 399-405. (LO13)

213

Kellerer, H., Tautenhahn, T., and Woeginger, G.J. (1996), ``Approximability and nonapproximability results for minimizing total flow time on a single machine'', Proc. 28th Ann. ACM Symp. on Theory of Comp. , ACM, 418-426. (SS11)

214

Kenyon, C., and Rémila, E. (1996), ``Approximate strip packing'', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 31-36. (SR2)

215

Khanna, S., Linial, N., and Safra, S. (1993), ``On the hardness of approximating the chromatic number'', Proc. 2nd Israel Symp. on Theory of Computing and Systems , IEEE Computer Society, 250-260. (GT5)

216

Khanna, S., and Motwani, R. (1996), ``Toward a syntactic characterization of PTAS'', Proc. 28th Ann. ACM Symp. on Theory of Comp. , ACM, 329-337. (LO1)

217

Khanna, S., Motwani, R., Sudan, M., and Vazirani, U. (1994), ``On syntactic versus computational views of approximability'', Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 819-830. (GT2, SP4)

218

Khanna, S., Motwani, R., and Yao, F. F. (1995), ``Approximation algorithms for the largest common subtree problem'', Unpublished manuscript. (SR7)

219

Khuller, S. (1997), ``Approximation algorithms for finding highly connected subgraphs'', in Approximation algorithms for NP-hard problems , PWS Publishing Company, Boston, 236-265. (ND26)

220

Khuller, S., Pless, R., and Sussmann, Y. J. (1997), ``Fault tolerant k-center problems'', Proc. 3rd Italian Conf. on Algorithms and Complexity , Lecture Notes in Comput. Sci. 1203, Springer-Verlag, 37-48. (ND48)

221

Khuller, S., and Raghavachari, B. (1995), ``Improved approximation algorithms for uniform connectivity problems'', Proc. 27th Ann. ACM Symp. on Theory of Comp. , ACM, 1-10. (ND24, ND25)

222

Khuller, S., Raghavachari, B., and Rosenfeld, A. (1994), ``Localization in graphs'', Technical Report UMIACS-TR-94-92, University of Maryland, UMIACS. (GT49)

223

Khuller, S., Raghavachari, B., and Young, N. (1993), ``Maintaining directed reachability with few edges'', Technical Report UMIACS-TR-93-87, University of Maryland, UMIACS. (ND10)

224

Khuller, S., Raghavachari, B., and Young, N. (1995), ``Approximating the minimum equivalent digraph'', SIAM J. Comp. 24 , 859-872. (GT35)

225

Khuller, S., Raghavachari, B., and Young, N. (1996a), ``Low degree spanning trees of small weight'', SIAM J. Comp. 25 , 355-368. (ND3)

226

Khuller, S., Raghavachari, B., and Young, N. (1996b), ``On strongly connected digraphs with bounded cycle length'', Disc. Appl. Math. 69 , 281-289. (ND24, ND25, ND27)

227

Khuller, S., and Sussmann, Y. J. (1996), ``The capacitated k-center problem'', Proc. 4th Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 1136, Springer-Verlag, 152-166. (ND48)

228

Khuller, S., and Thurimella, R. (1993), ``Approximation algorithms for graph augmentation'', J. Algorithms 14 , 214-225. (ND26)

229

Khuller, S., and Vishkin, U. (1994), ``Biconnectivity approximations and graph carvings'', J. ACM 41 , 214-235. (ND9, ND25)

230

Kierstead, H.A. (1991), ``A polynomial time approximation algorithm for dynamic storage allocation'', Disc. Math. 88 , 231-237. (SR3)

231

Kim, S., and McNaughton, R. (1993), ``Computing the order of a locally testable automaton'', Unpublished manuscript. (AL4)

232

Klein, P., Agrawal, A., Ravi, R., and Rao, S. (1990), ``Approximation through multicommodity flow'', Proc. 31st Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 726-737. (GT37, PO1)

233

Klein, P., Plotkin, S. A., and Rao, S. (1993), ``Excluded minors, network decomposition, and multicommodity flow'', Proc. 25th Ann. ACM Symp. on Theory of Comp. , ACM, 682-690. (ND20)

234

Kleinberg, J., and Tardos, É. (1995), ``Approximations for the disjoint paths problem in high-diameter planar networks'', Proc. 27th Ann. ACM Symp. on Theory of Comp. , ACM, 26-35. (ND44)

235

Kloks, T., Kratsch, D., and Müller, H. (1995), ``Approximating the bandwidth for asteroidal triple-free graphs'', Proc. 3rd Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 979, Springer-Verlag, 434-447. (GT39)

236

Ko, M. T., Lee, R. C. T., and Chang, J. S. (1990), ``An optimal approximation algorithm for the rectilinear m -center problem'', Algorithmica 5 , 341-352. (ND48)

237

Kohli, R., Krishnamurti, R., and Mirchandani, P. (1994), ``The minimum satisfiability problem'', SIAM J. Disc. Math. 7 , 275-283. (LO2, LO3)

238

Kolaitis, P. G., and Thakur, M. N. (1994), ``Logical definability of NP optimization problems'', Inform. and Comput. 115 , 321-353. (LO5)

239

Kolaitis, P. G., and Thakur, M. N. (1995), ``Approximation properties of NP minimization classes'', J. Comput. System Sci. 50 , 391-411. (GT24, GT25)

240

Kortsarz, G., and Peleg, D. (1992a), ``Approximation algorithms for minimum time broadcast'', Proc. 1st Israel Symp. on Theory of Computing and Systems , Lecture Notes in Comput. Sci. 601, Springer-Verlag, 67-78. (ND47)

241

Kortsarz, G., and Peleg, D. (1992b), ``Generating sparse 2-spanners'', Proc. 3rd Scandinavian Workshop on Algorithm Theory , Lecture Notes in Comput. Sci. 621, Springer-Verlag, 73-82. (GT33)

242

Kortsarz, G., and Peleg, D. (1993), ``On choosing a dense subgraph'', Proc. 34th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 692-701. (GT32)

243

Kortsarz, G., and Peleg, D. (1994), ``Generating low-degree 2-spanners'', Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 556-563. (GT33)

244

Kortsarz, G., and Peleg, D. (1997), ``Approximating shallow-light trees'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 103-110. (ND7)

245

Kosaraju, S. R., Park, J. K., and Stein, C. (1994), ``Long tours and short superstrings'', Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 166-177. (ND29)

246

Kou, L. T., Stockmeyer, L. J., and Wong, C. K. (1978), ``Covering edges by cliques with regard to keyword conflicts and intersection graphs'', Communications of the ACM 21 , 135-139. (GT15)

247

Lam, S., and Sethi, R. (1977), ``Worst case analysis of two scheduling algorithms'', SIAM J. Comp. 6 , 518-536. (SS7)

248

Leighton, T., and Rao, S. (1988), ``An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms'', Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 422-431. (GT40, GT41, ND23)

249

Lenstra, J. K., and Kan, A. H. G. Rinnooy (1978), ``Complexity of scheduling under precedence constraints'', Oper. Res. 26 , 22-35. (SS7)

250

Lenstra, J. K., and Shmoys, D. B. (1995), ``Computing near-optimal schedules'', in Scheduling theory and its applications , Wiley, Chichester, to appear. (SS14)

251

Lenstra, J. K., Shmoys, D. B., and Tardos, É. (1990), ``Approximation algorithms for scheduling unrelated parallel machines'', Math. Programming 46 , 259-271. (SS6)

252

Leonardi, S., and Raz, D. (1997), ``Approximating total flow time on parallel machines'', Proc. 29th Ann. ACM Symp. on Theory of Comp. , ACM, to appear. (SS11)

253

Levcopoulos, C., and Gudmundsson, J. (1996), ``Approximation algorithms for covering polygons with squares and similar problems'', Technical Report LU-CS-TR:96-181, Department of Computer Science, Lund University, Sweden. (SR9)

254

Li, C., McCormick, S. T., and Simchi-Levi, D. (1990), ``The complexity of finding two disjoint paths with min-max objective function'', Disc. Appl. Math. 26 , 105-115. (ND45)

255

Li, C., McCormick, S. T., and Simchi-Levi, D. (1992), ``On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems'', Oper. Res. Lett. 11 , 303-308. (ND28)

256

Li, K., and Cheng, K. (1990), ``On three-dimensional packing'', SIAM J. Comp. 19 , 847-867. (SR2)

257

Li, M. (1990), ``Towards a DNA sequencing theory'', Proc. 31st Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 125-134. (SR5)

258

Lin, C. (1994), ``Hardness of approximating graph transformation problem'', Proc. 5th Ann. Int. Symp. on Algorithms and Computation , Lecture Notes in Comput. Sci. 834, Springer-Verlag, 74-82. (GT45)

259

Lin, J-H., and Vitter, J. S. (1992), `` -approximations with minimum packing constraint violation'', Proc. 24th Ann. ACM Symp. on Theory of Comp. , ACM, 771-782. (ND52)

260

Lipton, R. J., and Tarjan, R. E. (1979), ``A separator theorem for planar graphs'', SIAM J. Appl. Math. 36 , 177-189. (ND22)

261

Lu, H., and Ravi, R. (1992), ``The power of local optimization: Approximation algorithms for maximum-leaf spanning tree'', Proc. Allerton Conf. , , 533-542. (ND4)

262

Ludwig, W., and Tiwari, P. (1994), ``Scheduling malleable and nonmalleable parallel tasks'', Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 167-176. (SS8)

263

Lund, C., and Yannakakis, M. (1993), ``The approximation of maximum subgraph problems'', Proc. 20th Int. Colloquium on Automata, Languages and Programming , Lecture Notes in Comput. Sci. 700, Springer-Verlag, 40-51. (GT23, GT24, GT26)

264

Lund, C., and Yannakakis, M. (1994), ``On the hardness of approximating minimization problems'', J. ACM 41 , 960-981. (GT2, GT5, GT13, GT15, GT16, SP4, SP5, SR1)

265

Mahajan, S., and J. Ramesh, 1995 (1995), ``Derandomizing semidefinite programming based approximation algorithms'', Proc. 36th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 162-169. (GT5, GT20, GT31, ND11, ND14)

266

Makedon, F., and Tragoudas, S. (1990), ``Approximating the minimum net expansion: near optimal solutions to circuit partitioning problems'', Proc. 16th Workshop on Graph-Theoretic Concepts in Computer Science , Lecture Notes in Comput. Sci. 484, Springer-Verlag, 140-153. (ND23)

267

Malesinska, Ewa, and Panconesi, Alessandro (1996), ``On the hardness of frequency allocation for hybrid networks'', Proc. 22nd Workshop on Graph-Theoretic Concepts in Computer Science , Lecture Notes in Comput. Sci. 1197, , 308-322. (MS14)

268

Marathe, M. V., Breu, H., Hunt III, H. B., Ravi, S. S., and Rosenkrantz, D. J. (1994), ``Simple heuristics for unit disk graphs'', Networks , to appear. (GT4, GT5)

269

Marathe, M. V., Ravi, R., Sundaram, R., Ravi, S. S., Rosenkrantz, D. J., and Hunt III, H. B. (1995), ``Bicriteria network design problems'', Proc. 22nd Int. Colloquium on Automata, Languages and Programming , Lecture Notes in Comput. Sci. 944, Springer-Verlag, 487-498. (ND47)

270

Maruyama, O., and Miyano, S. (1995), ``Graph inference from a walk for trees of bounded degree 3 is NP-complete'', Proc. 20th International Symp. on Mathematical Foundations of Comput. Sci. , Lecture Notes in Comput. Sci. 969, Springer-Verlag, 257-266. (GT51)

271

Michel, C., Schroeter, H., and Srivastav, A. (1995), ``Tsp and matching in printed circuit board assembly'', European Symposium on Operations Research , , . (ND30)

272

Middendorf, M. (1994), ``On the approximation of finding various minimal, maximal, and consistent sequences'', Proc. 5th Ann. Int. Symp. on Algorithms and Computation , Lecture Notes in Comput. Sci. 834, Springer-Verlag, 306-314. (SR4, SR6)

273

Mitchell, J. S. B., Piatko, C., and Arkin, E. M. (1992), ``Computing a shortest k -link path in a polygon'', Proc. 33rd Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 573-582. (MS6)

274

Mitchell, J. S. B., and Suri, S. (1992), ``Separation and approximation of polyhedral objects'', Proc. Third Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 296-306. (ND59)

275

Monien, B., and Speckenmeyer, E. (1985), ``Ramsey numbers and an approximation algorithm for the vertex cover problem'', Acta Informatica 22 , 115-123. (GT1)

276

Motwani, R., and Naor, J. S. (1994), ``On exact and approximate cut covers of graphs'', Technical Report STAN-CS-TN-94-11, Department of Computer Science, Stanford University. (GT19)

277

Nishizeki, T., Asano, T., and Watanabe, T. (1983), ``An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs'', Disc. Appl. Math. 5 , 211-222. (ND30)

278

Nishizeki, T., and Chiba, N. (1988), Planar Graphs: Theory and Algorithms , volume 32 of Annals of Disc. Math. , , Annals of Disc. Math., Elsevier science publishing company, Amsterdam. (GT23, SP1)

279

Nishizeki, T., and Kashiwagi, K. (1990), ``On the 1.1 edge-coloring of multigraphs'', SIAM J. Disc. Math. 3 , 391-410. (GT7)

280

Orponen, P., and Mannila, H. (1987), ``On approximation preserving reductions: Complete problems and robust measures'', Technical Report C-1987-28, Department of Computer Science, University of Helsinki. (ND29, MP1, LO7)

281

Panconesi, A., and Ranjan, D. (1993), ``Quantifiers and approximation'', Theoretical Computer Science 107 , 145-163. (GT34, LO6)

282

Papadimitriou, C. H. (1985), ``An algorithm for shortest-path motion in three dimensions'', Inform. Process. Lett. 20 , 259-263. (MS11)

283

Papadimitriou, C. H., Raghavan, P., Sudan, M., and Tamaki, H. (1994), ``Motion planning on a graph'', Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 511-520. (GP1)

284

Papadimitriou, C. H., and Yannakakis, M. (1991), ``Optimization, approximation, and complexity classes'', J. Comput. System Sci. 43 , 425-440. (GT1, GT2, GT9, GT21, GT31, ND11, ND13, SP4, LO1, LO2, LO4)

285

Papadimitriou, C. H., and Yannakakis, M. (1993), ``The traveling salesman problem with distances one and two'', Math. Oper. Res. 18 , 1-11. (ND30)

286

Park, J. K., and Phillips, C. A. (1993), ``Finding minimum-quotient cuts in planar graphs'', Proc. 25th Ann. ACM Symp. on Theory of Comp. , ACM, 766-775. (ND23)

287

Paz, A., and Moran, S. (1981), ``Non deterministic polynomial optimization problems and their approximations'', Theoretical Computer Science 15 , 251-277. (GT13)

288

Peleg, D., Schechtman, G., and Wool, A. (1993), ``Approximating bounded 0-1 integer linear programs'', Proc. 2nd Israel Symp. on Theory of Computing and Systems , IEEE Computer Society, 69-77. (SP4)

289

Petrank, E. (1992), ``The hardness of approximation: gap location'', Technical Report 754, Computer Science Department, Technion, Israel Institute of Technology, Haifa, Israel. (MS2)

290

Petrank, E. (1994), ``The hardness of approximation: gap location'', Computational Complexity 4 , 133-157. (GT1, GT7, SP3)

291

Phillips, C., Stein, C., and Wein, J. (1995), ``Scheduling jobs that arrive over time'', Proc. 4th Workshop on Algorithms and Data Structures , Lecture Notes in Comput. Sci. 955, Springer-Verlag, 86-97. (SS12)

292

Phillips, C. A. (1993), ``The network inhibition problem'', Proc. 25th Ann. ACM Symp. on Theory of Comp. , ACM, 776-785. (ND15, ND40)

293

Pitt, L., and Warmuth, M. K. (1993), ``The minimum consistent DFA problem cannot be approximated within any polynomial'', J. ACM 40 , 95-142. (AL1)

294

Plaisted, D. A., and Hong, J. (1987), ``A heuristic triangulation algorithm'', J. Algorithms 8 , 405-437. (ND58)

295

Plesník, J. (1980), ``On the computational complexity of centers locating in a graph'', Aplikace Matematiky 25 , 445-452. (ND48)

296

Plesník, J. (1981), ``The complexity of designing a network with minimum diameter'', Networks 11 , 77-85. (ND6)

297

Plesník, J. (1982), ``Complexity of decomposing graphs into factors with given diameters or radii'', Math. Slovaca 32 , 379-388. (ND53)

298

Plesník, J. (1987), ``A heuristic for the p -center problem in graphs'', Disc. Appl. Math. 17 , 263-268. (ND48)

299

Plesník, J. (1988), ``Two heuristics for the absolute p-center problem in graphs'', Math. Slovaca 38 , 227-233. (ND48)

300

Provan, J. S. (1988), ``An approximation scheme for finding Steiner trees with obstacles'', SIAM J. Comp. 17 , 920-934. (ND8)

301

Queyranne, M. (1985), ``Bounds for assembly line balancing heuristics'', Oper. Res. 33 , 1353-1359. (SR1)

302

Queyranne, M. (1986), ``Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems'', Oper. Res. Lett. 4 , 231-234. (MP7)

303

Rabani, Y. (1996), ``Path coloring on the mesh'', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 400-409. (ND44)

304

Raghavan, P., and Thompson, C. D. (1991), ``Multiterminal global routing: A deterministic approximation scheme'', Algorithmica 6 , 73-82. (ND41)

305

Raghavan, P., and Upfal, E. (1994), ``Efficient routing in all-optical networks'', Proc. 26th Ann. ACM Symp. on Theory of Comp. , ACM, 134-143. (ND44)

306

Ravi, R. (1994a), ``A primal-dual approximation algorithm for the Steiner forest problem'', Inform. Process. Lett. 50 , 185-190. (ND7)

307

Ravi, R. (1994b), ``Rapid rumor ramification: approximating the minimum broadcast time'', Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 202-213. (ND47)

308

Ravi, R., Agrawal, A., and Klein, P. (1991), ``Ordering problems approximated: single-processor scheduling and interval graph completion'', Automata, Languages and Programming , Lecture Notes in Comput. Sci. 510, Springer-Verlag, 751-762. (GT36, SS2)

309

Ravi, R., Sundaram, R., Marathe, M. V., Rosenkrantz, D. J., and Ravi, S. S. (1994), ``Spanning trees short or small'', Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 546-555. (ND1, ND7)

310

Ravi, R., and Williamson, D. (1995), ``An approximation algorithm for minimum-cost vertex-connectivity problems'', Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 332-341. (ND24)

311

Ravi, S. S., Rosenkrantz, D. J., and Tayi, G. K. (1991), ``Facility dispersion problems: heuristics and special cases'', Proc. 2nd Workshop on Algorithms and Data Structures , Lecture Notes in Comput. Sci. 519, Springer-Verlag, 355-366. (ND54)

312

Rayward-Smith, V. J. (1987), ``Net scheduling with unit interprocessor communication delays'', Disc. Appl. Math. 18 , 55-71. (SS7)

313

Sahni, S. K., and Gonzalez, T. F. (1976), ``P-complete approximation problems'', J. ACM 23 , 555-565. (GT17, GT18, ND50, MP6, MP7)

314

Salman, F. S., Cheriyan, J., Ravi, R., and Subramanian, S. (1997), ``Buy-at-bulk network design: approximating the single-sink edge installation problem'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 619-628. (ND46)

315

Saran, H., and Vazirani, V. (1991), ``Finding k -cuts within twice the optimal'', Proc. 32nd Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 743-751. (ND16)

316

Schiermeyer, I. (1994), ``Reverse-fit: a 2-optimal algorithm for packing rectangles'', Proc. 2nd Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 855, Springer-Verlag, 290-299. (SR2)

317

Seymour, P. D. (1995), ``Packing directed circuits fractionally'', Combinatorica 15 , 281-288. (GT8)

318

Seymour, P. D., and Thomas, R. (1994), ``Call routing and the ratcatcher'', Combinatorica 14 , 217-241. (ND10)

319

Shmoys, D. B. (1997), ``Cut problems and their application to divide-and-conquer'', in Approximation algorithms for NP-hard problems , PWS Publishing Company, Boston, 192-235. (ND21)

320

Shmoys, D. B., Stein, C., and Wein, J. (1994), ``Improved approximation algorithms for shop scheduling problems'', SIAM J. Comp. 23 , 617-632. (SS17)

321

Shmoys, D. B., and Tardos, É. (1993), ``Scheduling unrelated machines with costs'', Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 448-454. (SS6)

322

Simchi-Levi, D. (1994), ``New worst-case results for the bin-packing problem'', Naval Res. Logistics 41 , 579-585. (SR1)

323

Simon, H. U. (1989), ``Approximation algorithms for channel assignment in cellular radio networks'', Proc. Fundamentals of Computation Theory , Lecture Notes in Comput. Sci. 380, Springer-Verlag, 405-416. (MS5)

324

Simon, H. U. (1990), ``On approximate solutions for combinatorial optimization problems'', SIAM J. Disc. Math. 3 , 294-310. (GT15, GT16, AL1)

325

Skutella, M. (1997), ``Approximation algorithms for the discrete time-cost tradeoff problem'', Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 501-508. (SS5)

326

Slusarek, M. (1989), ``A coloring algorithm for interval graphs'', Proc. 14th International Symp. on Mathematical Foundations of Comput. Sci. , Lecture Notes in Comput. Sci. 379, Springer-Verlag, 471-480. (SR3)

327

Srinivasan, A. (1995), ``Improved approximations of packing and covering problems'', Proc. 27th Ann. ACM Symp. on Theory of Comp. , ACM, 268-276. (SP4, MP3, MP4)

328

Srivastav, A., and Stangier, P. (1994), ``Tight approximations for resource constrained sheduling problems'', Proc. 2nd Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 855, Springer-Verlag, 307-318. (SS8)

329

Tamir, A. (1991), ``Obnoxious facility location on graphs'', SIAM J. Disc. Math. 4 , 550-567. (ND54)

330

Tarhio, J., and Ukkonen, E. (1988), ``A greedy approximation algorithm for constructing shortest common superstrings'', Theoretical Computer Science 57 , 131-145. (SR5)

331

Trevisan, L. (1996), ``Positive linear programming, parallel approximation and PCP¹s'', Proc. 4th Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 1136, Springer-Verlag, 62-75. (LO12)

332

Trevisan, L. (1997), ``When Hamming meets Euclid: the approximability of geometric tsp and mst'', Proc. 29th Ann. ACM Symp. on Theory of Comp. , ACM, . (ND31)

333

Trevisan, L., Sorkin, G. B:, Sudan, M., and Williamson, D. P. (1996), ``Gadgets, approximation, and linear programming'', Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, 617-626. (LO2)

334

Turek, J., Schwiegelshohn, U., Wolf, J. L., and Yu, P. S. (1994), ``Scheduling paralle tasks to minimize average response time'', Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 112-121. (SS8)

335

Turner, J. S. (1989), ``Approximation algorithms for the shortest common superstring problem'', Inform. and Comput. 83 , 1-20. (SR5)

336

Verbitsky, O. (1994), ``On the largest common subgraph problem'', Unpublished manuscript. (GT42)

337

Verbitsky, O. (1995), ``On the hardness of approximating some optimization problems that are supposedly easier than Max Clique'', Combinatorics, Probability and Computing 4 , 167-180. (GT11, GT21, LO12)

338

Vishwanathan, S. (1992), ``An approximation algorithm for the asymmetric travelling salesman problem with distances one and two'', Inform. Process. Lett. 44 , 297-302. (ND30)

339

Vishwanathan, S. (1996), ``An approximation algorithm for the asymmetric p -center problem'', Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms , ACM-SIAM, 1-5. (ND48)

340

Vizing, V. G. (1964), ``On an estimate of the chromatic class of a p-graph'', Diskret. Analiz. 3 , 23-30. (GT7)

341

Wagner, F., and Wolff, A. (1995), ``An efficient and effective approximation algorithm for the map labeling problem'', Proc. 3rd Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 979, Springer-Verlag, 420-433. (MS12)

342

Wang, Q., and Cheng, K.H. (1990), ``A heuristic algorithm for the k-center problem with cost and usage weights'', Technical Report TR #UH-CS-90-15, Computer Science Department, Houston University. (ND51)

343

Wee, T. S., and Magazine, M. J. (1982), ``Assembly line balancing as generalized bin packing'', Oper. Res. Lett. 1 , 56-58. (SR1)

344

Williamson, D. P., Goemans, M. X., Mihail, M., and Vazirani, V. V. (1995), ``A primal-dual approximation algorithm for generalized Steiner network problems'', , , 435-454. (ND9)

345

Williamson, D. P., Hall, L. A., Hoogeveen, J. A., Hurkens, C. A. J., Lenstra, J. K., and Shmoys, D. B. (1994), ``Short shop schedules'', Unpublished manuscript. (SS14, SS15, SS17)

346

Wöginger, G. J., and Yu, Z. (1992), ``A heuristic for preemptive scheduling with set-up times'', Computing 49 , 151-158. (SS9)

347

Yannakakis, M. (1979), ``The effect of a connectivity requirement on the complexity of maximum subgraph problems'', J. ACM 26 , 618-630. (GT27)

348

Yu, B., and Cheriyan, J. (1995), ``Approximation algorithms for feasible cut and multicut problems'', Proc. 3rd Ann. European Symp. on Algorithms , Lecture Notes in Comput. Sci. 979, Springer-Verlag, 394-408. (ND19)

349

Yue, M. (1991), ``A simple proof of the inequality for the MFFD bin-pack algorithm'', Technical Report RRR # 20-91, Rutcor, Rutgers Center for Operations Research, Rutgers University, New Jersey. (SR1)

350

Zelikovsky, A. Z. (1994), ``Better approximation bounds for the network and Euclidean Steiner tree problems'', Unpublished manuscript. (ND8)

351

Zhang, K., and Jiang, T. (1994), ``Some MAX SNP-hard results concerning unordered labeled trees'', Inform. Process. Lett. 49 , 249-254. (GT44)

352

Zuckerman, D. (1993), ``NP-complete problems have a version that's hard to approximate'', Proc. Eight Ann. Structure in Complexity Theory Conf. , IEEE Computer Society, 305-312. (GT1, GT5, GT8, GT9, GT15, GT38, ND7, ND14, SP1, SP4, SP7, SP9, SS1)