next up previous index
Next: Index Up: A compendium of NP Previous: MINIMUM RING LOADING   Index

Bibliography

1
Agarwal, P. K., and Procopiuc, C. M. (1998),
``Exact and approximation algorithms for clustering'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 658-667.
(MINIMUM K-CENTER)

2
Agarwal, P. K., and Suri, S. (1994),
``Surface approximation and geometric partitions'',
Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 34-43.
(MINIMUM RED-BLUE SEPARATION)

3
Agarwala, R., Bafna, V., Farach, M., Narayanan, B., Paterson, M., and Thorup, M. (1996),
``On the approximability of numerical taxonomy'',
Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 365-372.
(MINIMUM NUMERICAL TAXONOMY)

4
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.
(MINIMUM GEOMETRIC TRAVELING SALESPERSON)

5
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.
(MINIMUM GENERALIZED STEINER NETWORK)

6
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.
(MAXIMUM COMMON SUBTREE, MAXIMUM COMMON POINT SET)

7
Akutsu, T., and Halldórsson, M. (1997),
``On the approximation of largest common point sets and largest common subtrees'',
Unpublished manuscript.
(MAXIMUM COMMON SUBTREE)

8
Alekhnovich, M., Buss, S., Moran, S., and Pitassi, T. (1998),
``Minimum propositional proof length is NP-hard to linearly approximate'',
Proc. 23rd International Symp. on Mathematical Foundations of Comput. Sci., Lecture Notes in Comput. Sci. 1450, Springer-Verlag, 176-184.
(MINIMUM LENGTH EQUIVALENT FREGE PROOF)

9
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.
(MINIMUM VERTEX COVER, MAXIMUM CUT)

10
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.
(MINIMUM PARALLEL PROCESSOR TOTAL FLOW TIME)

11
Alon, N., Csirik, J., Sevastianov, S. V., Vestjens, A. P. A., and Woeginger, G. J. (1996),
``On-line and off-line approximation algorithms for vector covering problems'',
Proc. 4th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1136, Springer-Verlag, 406-418.
(MAXIMUM D-VECTOR COVERING)

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

13
Alon, N., and Kahale, N. (1994),
``Approximating the independence number via the $\theta$-function'',
Unpublished manuscript.
(MAXIMUM CLIQUE, MAXIMUM INDEPENDENT SET)

14
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.
(LONGEST PATH)

15
Amaldi, E., and Kann, V. (1995),
``The complexity and approximability of finding maximum feasible subsystems of linear relations'',
Theoretical Comput. Sci. 147, 181-210.
(MAXIMUM SATISFYING LINEAR SUBSYSTEM, MAXIMUM HYPERPLANE CONSISTENCY, MAXIMUM SATISFIABILITY OF QUADRATIC EQUATIONS OVER GF[Q])

16
Amaldi, E., and Kann, V. (1998),
``On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems'',
Theoretical Comput. Sci. 209, 237-260.
(MINIMUM RELEVANT VARIABLES IN LINEAR SYSTEM, MINIMUM UNSATISFYING LINEAR SUBSYSTEM, MAXIMUM HYPERPLANE CONSISTENCY)

17
Amoura, A. K., Bampis, E., Kenyon, C., and Manoussakis, Y. (1997),
``How to schedule independent multiprocessor tasks'',
Proc. 5th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1284, Springer-Verlag, 1-12.
(MINIMUM 3-DEDICATED PROCESSOR SCHEDULING)

18
Andersson, G. (1999),
``An approximation algorithm for MAX p-SECTION'',
Proc. 16th Ann. Symp. on Theoretical Aspects of Comput. Sci., , Lecture Notes in Comput. Sci., Springer-Verlag, to appear.
(MAXIMUM K-CUT)

19
Andersson, G., and Engebretsen, L. (1998a),
``Better approximation algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT'',
Inform. Process. Lett. 65, 305-311.
(MAXIMUM SET SPLITTING, MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY)

20
Andersson, G., and Engebretsen, L. (1998b),
``Sampling methods applied to non-boolean optimization problems'',
Proc. 2nd Symp. on Randomization and Approximation Techniques in Comput. Sci., Lecture Notes in Comput. Sci. 1518, Springer-Verlag, 357-368.
(MAXIMUM SATISFYING LINEAR SUBSYSTEM, MAXIMUM K-CONSTRAINT SATISFACTION)

21
Andersson, G., Engebretsen, L., and Håstad, J. (1999),
``A new way to use semidefinite programming with applications to linear equations mod p'',
Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 41-50.
(MAXIMUM SATISFYING LINEAR SUBSYSTEM)

22
Andreae, T., and Bandelt, H. (1995),
``Performance guarantees for approximation algorithms depending on parametrized triangle inequalities'',
SIAM J. Disc. Math. 8, 1-16.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

23
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.
(MINIMUM BIN PACKING)

24
Anily, S., and Hassin, R. (1992),
``The swapping problem'',
Networks 22, 419-433.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

25
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.
(MINIMUM METRIC BOTTLENECK WANDERING SALESPERSON PROBLEM)

26
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.
(MINIMUM VERTEX COVER)

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

28
Arkin, E. M., and Hassin, R. (1994),
``Approximation algorithms for the geometric covering salesman problem'',
Disc. Appl. Math. 55, 197-218.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

29
Arkin, E. M., and Hassin, R. (1998),
``On local search for weighted packing probems'',
Math. Oper. Res. 23, 640-648.
(MAXIMUM 3-DIMENSIONAL MATCHING, MAXIMUM SET PACKING)

30
Armen, C., and Stein, C. (1994),
``A 2$\frac{3}{4}$-approximation algorithm for the shortest superstring problem'',
Technical Report PCS-TR94-214, Department of Computer Science, Dartmouth College, Hanover, New Hampshire.
(SHORTEST COMMON SUPERSTRING)

31
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.
(MINIMUM K-SPANNING TREE, MINIMUM GEOMETRIC 3-DEGREE SPANNING TREE, MINIMUM GEOMETRIC STEINER TREE, MINIMUM GEOMETRIC TRAVELING SALESPERSON)

32
Arora, S. (1997),
``Nearly linear time approximation schemes for Euclidean TSP and other geometric problems'',
Proc. 38th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 554-563.
(MINIMUM GEOMETRIC STEINER TREE, MINIMUM GEOMETRIC TRAVELING SALESPERSON)

33
Arora, S., Babai, L., Stern, J., and Sweedyk, Z. (1997),
``The hardness of approximate optima in lattices, codes, and systems of linear equation'',
J. Comput. System Sci. 54, 317-331.
(MAXIMUM SATISFYING LINEAR SUBSYSTEM, MINIMUM UNSATISFYING LINEAR SUBSYSTEM, MAXIMUM HYPERPLANE CONSISTENCY, NEAREST LATTICE VECTOR, NEAREST CODEWORD)

34
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.
(MINIMUM FEEDBACK ARC SET, MINIMUM LINEAR ARRANGEMENT, MINIMUM CUT LINEAR ARRANGEMENT, MAXIMUM BETWEENNESS)

35
Arora, S., Grigni, M., Karger, D., Klein, P., and Woloszyn, A. (1998),
``A polynomial-time approximation scheme for Weighted planar graph TSP'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 33-41.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

36
Arora, S., and Karakostas, G. (1999),
``Approximation schemes for minimum latency problems'',
Proc. 31st Ann. ACM Symp. on Theory of Comp., ACM, to appear.
(MINIMUM TRAVELING REPAIRMAN)

37
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.
(MAXIMUM K-COLORABLE SUBGRAPH, MAXIMUM EDGE SUBGRAPH, MAXIMUM CUT, MAXIMUM DIRECTED CUT, MINIMUM K-CUT, MINIMUM MULTIWAY CUT, MINIMUM B-BALANCED CUT, MAXIMUM SET SPLITTING, MAXIMUM K-SATISFIABILITY)

38
Asano, T., Hori, K., Ono, T., and Hirata, T. (1997),
``A theoretical framework of hybrid approaches to MAX SAT'',
Proc. 8th Ann. Int. Symp. on Algorithms and Computation, Lecture Notes in Comput. Sci. 1350, Springer-Verlag, 153-162.
(MAXIMUM SATISFIABILITY)

39
Assmann, S. F., Johnson, D. S., Kleitman, D. J., and Leung, J. Y. (1984),
``On a dual version of the one-dimensional bin packing problem'',
J. Algorithms 5, 502-525.
(MAXIMUM D-VECTOR COVERING)

40
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.
(MAXIMUM DISJOINT CONNECTING PATHS)

41
Aumann, Y., and Rabani, Y. (1998),
``An $o(\log k)$ approximate min-cut max-flow theorem and approximation algorithm'',
SIAM J. Comp. 27, 291-301.
(MINIMUM RATIO-CUT)

42
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., and Protasi, M. (1999),
Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties,
Springer-Verlag, Berlin.
(MAXIMUM K-SATISFIABILITY)

43
Ausiello, G., D'Atri, A., and Protasi, M. (1980),
``Structure preserving reductions among convex optimization problems'',
J. Comput. System Sci. 21, 136-153.
(MINIMUM FEEDBACK VERTEX SET, MAXIMUM SET PACKING, MINIMUM SET COVER, MINIMUM HITTING SET)

44
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.
(MAXIMUM DISTINGUISHED ONES)

45
Averbakh, I., and Berman, O. (1997),
``(p-1)/(p+1)-approximate algorithms for p-traveling salesmen problems on a tree with minmax objective'',
Disc. Appl. Math. 75, 201-216.
(MINIMUM METRIC TRAVELING K-SALESPERSON PROBLEM)

46
Awerbuch, B., and Azar, Y. (1997),
``Buy-at-bulk network design'',
Proc. 38th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 542-547.
(MINIMUM SINGLE-SINK EDGE INSTALLATION)

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

48
Bafna, V., Lawler, E. L., and Pevzner, P. A. (1997),
``Approximation algorithms for multiple sequence alignment'',
Theoretical Comput. Sci. 182, 233-244.
(MINIMUM TREE ALIGNMENT)

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

50
Baker, B. S. (1994),
``Approximation algorithms for NP-complete problems on planar graphs'',
J. ACM 41, 153-180.
(MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM EDGE DOMINATING SET, MAXIMUM TRIANGLE PACKING, MAXIMUM H-MATCHING, MAXIMUM INDEPENDENT SET, MAXIMUM K-COLORABLE INDUCED SUBGRAPH)

51
Bandelt, H., Crama, Y., and Spieksma, F. C. R. (1994),
``Approximation algorithms for multi-dimensional assignment problems with decomposable costs'',
Disc. Appl. Math. 49, 25-50.
(MINIMUM 3-DIMENSIONAL ASSIGNMENT)

52
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.
(MINIMUM STEINER TREE)

53
Bar-Ilan, J., and Peleg, D. (1991),
``Approximation algorithms for selecting network centers'',
Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 519, Springer-Verlag, 343-354.
(MINIMUM K-CENTER)

54
Bar-Noy, A., Bellare, M., Halldórsson, M. M., Shachnai, H., and Tamir, T. (1998),
``On chromatic sums and distributed resource allocation'',
Inform. and Comput. 140, 183-202.
(MINIMUM COLOR SUM)

55
Bar-Noy, A., and Kortsarz, G. (1998),
``The minimum color sum of bipartite graphs'',
J. Algorithms 28, 339-365.
(MINIMUM COLOR SUM)

56
Bar-Yehuda, R., and Even, S. (1981),
``A linear-time approximation algorithm for the weighted vertex cover problem'',
J. Algorithms 2, 198-203.
(MINIMUM VERTEX COVER, MINIMUM SET COVER)

57
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.
(MINIMUM VERTEX COVER)

58
Bar-Yehuda, R., and Moran, S. (1984),
``On approximation problems related to the independent set and vertex cover problems'',
Disc. Appl. Math. 9, 1-10.
(MINIMUM DOMINATING SET)

59
Bar-Yehuda, Reuven (1998),
``A linear time 2-approximation algorithm for the min clique-complement problem'',
Technical Report CS0933, Technion CS Technical Reports.
http://www.cs.technion.ac.il/i-res.html
(MINIMUM EDGE DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P)

60
Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., and Stougie, L. (1996),
``Multiprocessor scheduling with rejection'',
Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 95-103.
(MINIMUM MULTIPROCESSOR SCHEDULING)

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

62
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.
(LONGEST PATH, MAXIMUM PRIORITY FLOW, MAXIMUM CAPACITY REPRESENTATIVES)

63
Bellare, M., Goldreich, O., and Sudan, M. (1998),
``Free bits, PCPs and non-approximability - towards tight results'',
SIAM J. Comp. 27, 804-915.
(MINIMUM GRAPH COLORING, MAXIMUM CLIQUE, LONGEST COMMON SUBSEQUENCE, MAXIMUM COMPATIBLE BINARY CONSTRAINT SATISFACTION)

64
Bellare, M., and Rogaway, P. (1995),
``The complexity of approximating a nonlinear program'',
Math. Programming 69, 429-441.
(MAXIMUM QUADRATIC PROGRAMMING)

65
Bender, M. A., Chakrabarti, S., and Muthukrishnan, S. (1998),
``Flow and stretch metrics for scheduling continuous job streams'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 270-279.
(MINIMUM SEQUENCING WITH RELEASE TIMES)

66
Berger, B., and Cowen, L. (1991),
``Complexity results and algorithms for $\{<,\leq,=\}$-constrained scheduling'',
Proc. Second Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 137-147.
(MINIMUM PRECEDENCE CONSTRAINED SCHEDULING)

67
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.
(MINIMUM FEEDBACK ARC SET)

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

69
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.
(MINIMUM VERTEX COVER, MAXIMUM INDEPENDENT SET, MAXIMUM SET PACKING)

70
Berman, P., and Karpinski, M. (1998),
``On some tighter inapproximability results'',
Technical Report TR98-029, ECCC.
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1998/TR98-029/index.html
(MINIMUM VERTEX COVER, MAXIMUM INDEPENDENT SET, MAXIMUM SATISFYING LINEAR SUBSYSTEM, MAXIMUM K-SATISFIABILITY, MINIMUM SORTING BY REVERSALS)

71
Berman, P., and Schnitger, G. (1992),
``On the complexity of approximating the independent set problem'',
Inform. and Comput. 96, 77-94.
(MAXIMUM INDUCED CONNECTED SUBGRAPH WITH PROPERTY P, LONGEST PATH WITH FORBIDDEN PAIRS, LONGEST COMMON SUBSEQUENCE, MAXIMUM BOUNDED 0-1 PROGRAMMING, MAXIMUM K-CONSTRAINT SATISFACTION, LONGEST COMPUTATION)

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

73
Bernstein, D., Rodeh, M., and Gertner, I. (1989),
``Approximation algorithms for scheduling arithmetic expressions on pipelined machines'',
J. Algorithms 10, 120-139.
(MINIMUM PRECEDENCE CONSTRAINED SEQUENCING WITH DELAYS)

74
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.
(MINIMUM EDGE COLORING, MAXIMUM SATISFIABILITY, MINIMUM K-SATISFIABILITY)

75
Blache, G., Karpinski, M., and Wirtgen, J. (1998),
``On approximation intractability of the bandwidth problem'',
Technical Report TR98-014, ECCC.
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1998/TR98-014/index.html
(MINIMUM BANDWIDTH)

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

77
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.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

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

79
Blum, A., Ravi, R., and Vempala, S. (1996),
``A constant-factor approximation algorithm for the k-MST problem'',
Proc. 28th Ann. ACM Symp. on Theory of Comp., ACM, 442-448.
(MINIMUM STEINER TREE)

80
Blum, Avrim, and Karger, David (1997),
``An $\tilde{O}(n^{3/14})$-coloring algorithm for 3-colorable graphs'',
Inform. Process. Lett. 61, 49-53.
(MINIMUM GRAPH COLORING)

81
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.
(MINIMUM TREE WIDTH)

82
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.
(SHORTEST COMMON SUPERSEQUENCE, LONGEST COMMON SUBSEQUENCE)

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

84
Bshouty, N., and Burroughs, L. (1998),
``Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem'',
Proc. 15th Ann. Symp. on Theoretical Aspects of Comput. Sci., , Lecture Notes in Comput. Sci., Springer-Verlag, 298-308.
(MINIMUM VERTEX COVER)

85
Bui, T. N., and Jones, C. (1992),
``Finding good approximate vertex and edge partitions is NP-hard'',
Inform. Process. Lett. 42, 153-159.
(MINIMUM B-BALANCED CUT, MINIMUM B-VERTEX SEPARATOR)

86
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.
(MAXIMUM PLANAR SUBGRAPH)

87
Calinescu, G., Karloff, H., and Rabani, Y. (1998),
``An improved approximation algorithm for multiway cut'',
Proc. 30th Ann. ACM Symp. on Theory of Comp., ACM-SIAM, 48-52.
(MINIMUM MULTIWAY CUT)

88
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.
(MINIMUM WEIGHTED COMPLETION TIME SCHEDULING)

89
Chandra, A. K., Hirschberg, D. S., and Wong, C. K. (1976),
``Approximate algorithms for some generalized knapsack problems'',
Theoretical Comput. Sci. 3, 293-304.
(MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK, MAXIMUM INTEGER K-CHOICE KNAPSACK)

90
Chandra, B., and Halldórsson, M. M. (1999),
``Greedy local improvement and weighted set packing approximation'',
Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 169-176.
(MAXIMUM H-MATCHING, MAXIMUM SET PACKING)

91
Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., and Li, M. (1998),
``Approximation algorithms for directed Steiner problems'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 192-200.
(MINIMUM STEINER TREE, MINIMUM GENERALIZED STEINER NETWORK)

92
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.
(MAXIMUM ACHROMATIC NUMBER)

93
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.
(MINIMUM SEQUENCING WITH RELEASE TIMES)

94
Chen, B. (1993),
``A better heuristic for preemptive parallel machine scheduling with batch setup times'',
SIAM J. Comp. 22, 1303-1318.
(MINIMUM PREEMPTIVE SCHEDULING WITH SET-UP TIMES)

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

96
Chen, B., Glass, C. A., Potts, C. N., and Strusevich, V. A. (1996),
``A new heuristic for three-machine flow shop scheduling'',
Oper. Res. 44, 891-898.
(MINIMUM FLOW-SHOP SCHEDULING)

97
Chen, B., Potts, C. N., and Strusevich, V. A. (1995),
``Approximation algorithms for two-machine flow shop scheduling with batch setup times'',
Math. Programming , to appear.
(MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING WITH BATCH SET-UP TIMES)

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

99
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.
(MINIMUM OPEN-SHOP SCHEDULING)

100
Chen, Z.-Z. (1996),
``Practical approximation schemes for maximum induced-subgraph problems on K3,3-free or K5-free graphs'',
Proc. 23rd Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1099, Springer-Verlag, 268-279.
(MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P)

101
Cheriyan, J., and Thurimella, R. (1996),
``Approximating minimum-size k-connected spanning subgraphs via matching'',
Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 292-301.
(MINIMUM K-VERTEX CONNECTED SUBGRAPH, MINIMUM K-EDGE CONNECTED SUBGRAPH)

102
Chlebikova, J. (1996),
``Approximability of the Maximally balanced connected partition problem in graphs'',
Inform. Process. Lett. 60, 225-230.
(MAXIMUM BALANCED CONNECTED PARTITION, MAXIMUM LEAF SPANNING TREE)

103
Choi, J., Sellen, J., and Yap, C. K. (1997),
``Approximate Euclidean shortest paths in 3-space'',
International J. Comput. Geom. Appl. 7, 271-295.
(SHORTEST PATH MOTION IN 3 DIMENSIONS)

104
Chor, B., and Sudan, M. (1998),
``A geometric approach to betweenness'',
SIAM J. Disc. Math. 11, 511-523.
(MAXIMUM BETWEENNESS)

105
Christie, D. A. (1998),
``A 3/2-approximation algorithm for Sorting by reversals'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 244-252.
(MINIMUM SORTING BY REVERSALS)

106
Christofides, N. (1976),
``Worst-case analysis of a new heuristic for the travelling salesman problem'',
Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

107
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.
(MINIMUM PRECEDENCE CONSTRAINED SCHEDULING)

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

109
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.
(MINIMUM SCHEDULE LENGTH)

110
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.
(MINIMUM VERTEX COVER)

111
Cody, R. A., and Coffman, E. G., Jr (1976),
``Record allocation for minimizing expected retrieval costs on drum-like storage devices'',
J. ACM 23, 103-115.
(MINIMUM SUM OF SQUARES)

112
Coffman, E. G., Jr, Garey, M. R., and Johnson, D. S. (1997),
``Approximation algorithms for bin-packing - a survey'', in
Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, 46-93.
(MINIMUM BIN PACKING)

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

114
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.
(MAXIMUM K-FACILITY LOCATION)

115
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.
(MINIMUM GRAPH COLORING)

116
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.
(MINIMUM 3-DIMENSIONAL ASSIGNMENT)

117
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.
(MINIMUM EDGE COLORING, MINIMUM DEGREE SPANNING TREE, MINIMUM BIN PACKING)

118
Crescenzi, P., and Panconesi, A. (1991),
``Completeness in approximation classes'',
Inform. and Comput. 93, 241-262.
(MAXIMUM WEIGHTED SATISFIABILITY WITH BOUND)

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

120
Crescenzi, P., Silvestri, R., and Trevisan, L. (1996),
``To weight or not to weight: Where is the question?'',
Proc. 4th Israel Symp. on Theory of Computing and Systems, IEEE Computer Society, 68-77.
(MAXIMUM CUT, MAXIMUM DIRECTED CUT, MAXIMUM SATISFIABILITY, MAXIMUM K-SATISFIABILITY)

121
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.

122
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.
(MINIMUM MULTIWAY CUT)

123
d'Anzeo, C. (1996),
``Optimization complexity of the SCS problem given a longest common subsequence'',
Unpublished manuscript.
(SHORTEST COMMON SUPERSEQUENCE)

124
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.
(MINIMUM PHYLOGENETIC TREE DISTANCE)

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

126
Di Ianni, M. (1998),
``Efficient delay routing'',
Theoretical Comput. Sci. 196, 131-151.
(MINIMUM SCHEDULE LENGTH)

127
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.
(MAXIMUM MAP LABELING)

128
Drangmeister, K. U., Krumke, S. O., Marathe, M. V., Noltemeier, H., and Ravi, S. S. (1998),
``Modifying edges of a network to obtain short subgraphs'',
Theoretical Comput. Sci. 203, 91-121.
(MINIMUM STEINER TREE)

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

130
Duh, R., and Fürer, M. (1997),
``Approximation of k-set cover by semi-local optimization'',
Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, 256-265.
(MINIMUM GRAPH COLORING, MINIMUM CLIQUE PARTITION, MINIMUM CLIQUE COVER, MINIMUM SET COVER)

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

132
Engebretsen, L. (1999),
``An explicit lower bound for TSP with distances one and two'',
Proc. 16th Ann. Symp. on Theoretical Aspects of Comput. Sci., Lecture Notes in Comput. Sci. 1563, Springer-Verlag, 373-382.
http://www.nada.kth.se/~enge/forskning-en.html
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

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

134
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.
(MINIMUM DISTINGUISHED ONES)

135
Even, G., Naor, J., Rao, S., and Schieber, B. (1995),
``Divide-and-conquer approximation algorithms via spreading metrics'',
Proc. 36th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 62-71.
(MINIMUM CUT LINEAR ARRANGEMENT)

136
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.
(MINIMUM B-BALANCED CUT)

137
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.
(MINIMUM FEEDBACK VERTEX SET, MINIMUM FEEDBACK ARC SET)

138
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.
(MINIMUM FEEDBACK VERTEX SET)

139
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.
(MINIMUM SIZE ULTRAMETRIC TREE)

140
Farach, M., and Liberatore, V. (1998),
``On local register allocation'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 564-573.
(MINIMUM LOCAL REGISTER ALLOCATION)

141
Feder, T., and Greene, D. H. (1988),
``Optimal algorithms for approximate clustering'',
Proc. 20th Ann. ACM Symp. on Theory of Comp., ACM, 434-444.
(MINIMUM METRIC BOTTLENECK WANDERING SALESPERSON PROBLEM, MINIMUM K-CENTER, MINIMUM K-CLUSTERING)

142
Feige, U. (1996),
``A threshold of $\ln n$ for approximating set cover'',
Proc. 28th Ann. ACM Symp. on Theory of Comp., ACM, 314-318.
(MINIMUM DOMINATING SET, MINIMUM SET COVER)

143
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.
(MAXIMUM DIRECTED CUT, MAXIMUM K-SATISFIABILITY)

144
Feige, U., and Kilian, J. (1996),
``Zero knowledge and the chromatic number'',
Proc. Eleventh Ann. IEEE Conf. on Comp. Complexity, IEEE Computer Society, 278-287.
(MINIMUM GRAPH COLORING, MINIMUM COLOR SUM)

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

146
Fekete, S., Khuller, S., Klemmstein, M., Raghavachari, B., and Young, N. (1996),
``A network-flow technique for finding low-weight bounded-degree spanning trees'',
Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization, Lecture Notes in Comput. Sci. 1084, Springer-Verlag, 105-117.
(MINIMUM GEOMETRIC 3-DEGREE SPANNING TREE)

147
Feo, T., Goldschmidt, O., and Khellaf, M. (1992),
``One half approximation algorithms for the k-partition problem'',
Oper. Res. 40, 170-172.
(MINIMUM K-CLUSTERING SUM)

148
Feo, T., and Khellaf, M. (1990),
``A class of bounded approximation algorithms for graph partitioning'',
Networks 20, 181-195.
(MINIMUM K-CLUSTERING SUM)

149
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.
(MINIMUM K-EDGE CONNECTED SUBGRAPH)

150
Fernandez de la Vega, W., and Karpinski, M. (1998),
``Polynomial time approximation of dense weighted instances of MAX-CUT'',
Technical Report TR98-064, ECCC.
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1998/TR98-064/index.html
(MAXIMUM CUT)

151
Fernandez de la Vega, W., and Kenyon, C. (1998),
``A randomized approximation scheme for metric MAX-CUT'',
Proc. 39th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 468-471.
(MAXIMUM CUT)

152
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.
(MINIMUM HEIGHT TWO DIMENSIONAL PACKING)

153
Fialko, S., and Mutzel, P. (1998),
``A new approximation algorithm for the Planar augmentation problem'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 260-269.
(MINIMUM BICONNECTIVITY AUGMENTATION)

154
Floréen, P., and Orponen, P. (1993),
``Attraction radii in binary Hopfield nets are hard to compute'',
Neural Comput. 5, 812-821.
(MINIMUM ATTRACTION RADIUS FOR BINARY HOPFIELD NET)

155
Formann, M., and Wagner, F. (1991),
``A packing problem with applications to lettering of maps'',
Proc. 7th Ann. ACM Symp. Comput. Geom., ACM, 281-288.
(MAXIMUM MAP LABELING)

156
Fraser, C. B., and Irving, R. W. (1995),
``Approximation algorithms for the shortest common supersequence'',
Nordic J. Comp. 2, 303-325.
(SHORTEST COMMON SUPERSEQUENCE)

157
Fraser, C. B., Irving, R. W., and Middendorf, M. (1996),
``Maximal common subsequences and minimal common supersequences'',
Inform. and Comput. 124, 145-153.
(LONGEST COMMON SUBSEQUENCE)

158
Frederickson, G. N. (1979),
``Approximation algorithms for some postman problems'',
J. ACM 26, 538-554.
(MINIMUM CHINESE POSTMAN FOR MIXED GRAPHS)

159
Frederickson, G. N., Hecht, M. S., and Kim, C. E. (1978),
``Approximation algorithms for some routing problems'',
SIAM J. Comp. 7, 178-193.
(MINIMUM METRIC TRAVELING K-SALESPERSON PROBLEM, MINIMUM K-CHINESE POSTMAN PROBLEM, MINIMUM STACKER CRANE PROBLEM, MINIMUM K-STACKER CRANE PROBLEM)

160
Frederickson, G. N., and Jájá, J. (1981),
``Approximation algorithms for several graph augmentation problems'',
SIAM J. Comp. 10, 270-283.
(MINIMUM BICONNECTIVITY AUGMENTATION, MINIMUM STRONG CONNECTIVITY AUGMENTATION)

161
Frederickson, G. N., and Jájá, J. (1982),
``On the relationship between the biconnectivity augmentation and traveling salesman problems'',
Theoretical Comput. Sci. 19, 189-201.
(MINIMUM K-VERTEX CONNECTED SUBGRAPH, MINIMUM BICONNECTIVITY AUGMENTATION)

162
Frederickson, G. N., and Solis-Oba, R. (1996),
``Increasing the weight of minimum spanning trees'',
Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 539-546.
(MAXIMUM MINIMUM SPANNING TREE DELETING K EDGES)

163
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.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

164
Frieze, A., and Jerrum, M. (1997),
``Improved approximation algorithms for MAX k-CUT and MAX BISECTION'',
Algorithmica 18, 67-81.
(MAXIMUM K-COLORABLE SUBGRAPH, MAXIMUM CUT, MAXIMUM K-CUT)

165
Fujito, T. (1996),
``A unified local ratio approximation of node-deletion problems'',
Proc. 4th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1136, Springer-Verlag, 167-178.
(MINIMUM VERTEX DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P)

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

167
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.
(MAXIMUM LEAF SPANNING TREE)

168
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.
(MAXIMUM LEAF SPANNING TREE)

169
Garey, M. R., and Graham, R. L. (1975),
``Bounds for multiprocessor scheduling with resource constraints'',
SIAM J. Comp. 4, 187-200.
(MINIMUM RESOURCE CONSTRAINED SCHEDULING)

170
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.
(MINIMUM DEGREE SPANNING TREE, MINIMUM BIN PACKING)

171
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.
(MINIMUM BEND NUMBER)

172
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.
(MINIMUM K-SPANNING TREE, MINIMUM TRAVELING REPAIRMAN)

173
Garg, N., Konjevod, G., and Ravi, R. (1998),
``A polylogarithmic approximation algorithm for the group Steiner tree problem'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 253-259.
(MINIMUM STEINER TREE)

174
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.
(MINIMUM K-VERTEX CONNECTED SUBGRAPH)

175
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.
(MINIMUM B-BALANCED CUT)

176
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.
(MINIMUM VERTEX DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P, MINIMUM VERTEX K-CUT, MINIMUM MULTIWAY CUT, MINIMUM MULTI-CUT)

177
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.
(MINIMUM EDGE DELETION K-PARTITION, MINIMUM MULTI-CUT, MINIMUM EQUIVALENCE DELETION)

178
Garg, N., Vazirani, V. V., and Yannakakis, M. (1997),
``Primal-dual approximation algorithms for integral flow and multicut in trees'',
Algorithmica 18, 3-20.
(MINIMUM MULTI-CUT, MAXIMUM INTEGRAL K-MULTICOMMODITY FLOW ON TREES, MINIMUM SET COVER)

179
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.
(MAXIMUM KNAPSACK, MAXIMUM INTEGER K-CHOICE KNAPSACK)

180
Gergov, J. (1996),
``Approximation algorithms for dynamic storage allocation'',
Proc. 4th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1136, Springer-Verlag, 52-61.
(MINIMUM DYNAMIC STORAGE ALLOCATION)

181
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.
(MINIMUM TREE COMPACT PACKING)

182
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.
(MINIMUM GENERALIZED STEINER NETWORK)

183
Goemans, M. X., and Kleinberg, J. M. (1996),
``An improved approximation ratio for the minimum latency problem'',
Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 152-158.
(MINIMUM TRAVELING REPAIRMAN)

184
Goemans, M. X., Queyranne, M., Schulz, A. S., Skutella, M., and Wang, Y. (1998),
``Single machine scheduling with release dates'',
Unpublished manuscript.
(MINIMUM SEQUENCING WITH RELEASE TIMES)

185
Goemans, M. X., and Williamson, D. P. (1995a),
``A general approximation technique for constrained forest problems'',
SIAM J. Comp. 24, 296-317.
(MINIMUM K-CAPACITATED TREE PARTITION, MINIMUM POINT-TO-POINT CONNECTION, MINIMUM STEINER TREE, MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

186
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.
(MAXIMUM CUT)

187
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.
(MINIMUM FEEDBACK VERTEX SET, MINIMUM FEEDBACK ARC SET, MINIMUM EDGE DELETION K-PARTITION)

188
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.
(MINIMUM JOB SHOP SCHEDULING)

189
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.
(MINIMUM K-CUT)

190
Gonzalez, T. F. (1985),
``Clustering to minimize the maximum intercluster distance'',
Theoretical Comput. Sci. 38, 293-306.
(MINIMUM K-CENTER, MINIMUM K-CLUSTERING)

191
Gonzalez, T. F., and Zheng, S. (1989),
``Improved bounds for rectangular and Guilhotine partitions'',
J. Symbolic Comput. 7, 591-610.
(MINIMUM PARTITION OF RECTANGLE WITH INTERIOR POINTS)

192
Gonzalez, T. F., and Zheng, S. (1990),
``Approximation algorithm for partitioning a rectangle with interior points'',
Algorithmica 5, 11-42.
(MINIMUM PARTITION OF RECTANGLE WITH INTERIOR POINTS)

193
Grigni, M., and Manne, F. (1996),
``On the complexity of the generalized block distribution'',
Proc. of Irregular'96, the third international workshop on parallel algorithms for irregularly structured problems, , Lecture Notes in Comput. Sci., Springer-Verlag, 319-326.
(MINIMUM ARRAY PARTITION)

194
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.
(MINIMUM BLOCK-ANGULAR CONVEX PROGRAMMING)

195
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.
(MINIMUM DOMINATING SET)

196
Guha, S., and Khuller, S. (1998),
``Greedy strikes back: Improved facility location algorithms'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 649-657.
(MINIMUM FACILITY LOCATION)

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

198
Guttmann-Beck, N., and Hassin, R. (1997),
``Approximation algorithms for min-max tree partition'',
J. Algorithms 24, 266-286.
(MINIMUM K-CAPACITATED TREE PARTITION)

199
Guttmann-Beck, N., and Hassin, R. (1998a),
``Approximation algorithms for minimum tree partition'',
Disc. Appl. Math. 87, 117-137.
(MINIMUM K-CAPACITATED TREE PARTITION)

200
Guttmann-Beck, N., and Hassin, R. (1998b),
``Approximation algorithms for minimum sum p-clustering'',
Disc. Appl. Math. 89, 125-142.
(MINIMUM K-CLUSTERING SUM)

201
Guttmann-Beck, N., and Hassin, R. (1999),
``Approximation algorithms for minimum k-cut'',
Algorithmica , to appear.
(MINIMUM K-CUT)

202
Guttmann-Beck, N., Hassin, R., Khuller, S., and Raghavachari, B. (1999),
``Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem'',
Algorithmica , to appear.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

203
Hall, L. A., Schulz, A. S., Shmoys, D. B., and Wein, J. (1997),
``On-line and off-line approximation algorithms'',
Unpublished manuscript.
http://www.orie.cornell.edu/~shmoys/swjCj-mor.ps
(MINIMUM SEQUENCING WITH RELEASE TIMES)

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

205
Halldórsson, M., and Lau, H. C. (1997),
``Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and 3-coloring'',
Journal of Graph Algorithms and Applications 1, 1-13.
(MAXIMUM INDEPENDENT SET, MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P)

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

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

208
Halldórsson, M. M. (1994),
``personal communication'',
Unpublished manuscript.
(MINIMUM CLIQUE COVER, MINIMUM COMPLETE BIPARTITE SUBGRAPH COVER, MAXIMUM K-COLORABLE INDUCED SUBGRAPH, MAXIMUM COMMON SUBGRAPH)

209
Halldórsson, M. M. (1995a),
``Approximating discrete collections via local improvements'',
Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 160-169.
(MINIMUM VERTEX COVER, MAXIMUM INDEPENDENT SET, MAXIMUM K-COLORABLE INDUCED SUBGRAPH)

210
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.
(LONGEST COMMON SUBSEQUENCE, MAXIMUM SATISFYING LINEAR SUBSYSTEM)

211
Halldórsson, M. M. (1999a),
``Approximations of independent set variants and hereditary subset problems'',
Unpublished manuscript.
(MAXIMUM CLIQUE, MAXIMUM INDEPENDENT SET, MAXIMUM INDEPENDENT SEQUENCE, MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P, MAXIMUM SET PACKING)

212
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.
(MAXIMUM MINIMUM METRIC K-SPANNING TREE)

213
Halldórsson, M. M., Kratochvíl, J., and Telle, J. A. (1998),
``Independent sets with domination constraints'',
Proc. 25th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1443, Springer-Verlag, 176-185.
(MINIMUM INDEPENDENT DOMINATING SET, MAXIMUM SET PACKING)

214
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, Springer-Verlag, 75-84.
(MAXIMUM COMMON EMBEDDED SUB-TREE)

215
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.
(MINIMUM STEINER TREE)

216
Hancock, T., Jiang, T., Li, M., and Tromp, J. (1996),
``Lower bounds on learning decision lists and trees'',
Inform. and Comput. 126, 114-122.
(MINIMUM DECISION TREE)

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

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

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

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

221
Hassin, R., and Rubinstein, S. (1997),
``An approximation algorithm for maximum packing of 3-edge paths'',
Information Processing Letters 63, 63-67.
http://www.math.tau.ac.il/ hassin
(MAXIMUM H-MATCHING)

222
Hassin, R., and Rubinstein, S. (1998a),
``Robust matchings, maximum clustering, and maximum capacitated medians'',
Proc. 1st Int. Conf. on Fun with Algorithms, , .
(MINIMUM K-CLUSTERING SUM)

223
Hassin, R., and Rubinstein, S. (1998b),
``Better approximations for Max TSP'',
Unpublished manuscript.
(MINIMUM TRAVELING SALESPERSON)

224
Hassin, R., Rubinstein, S., and Tamir, A. (1997),
``Approximation algorithms for maximum dispersion'',
Oper. Res. Lett. 21, 133-137.
(MAXIMUM EDGE SUBGRAPH)

225
Håstad, J. (1996),
``Clique is hard to approximate within $n^{1-\varepsilon }$'',
Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 627-636.
(MAXIMUM CLIQUE)

226
Håstad, J. (1997),
``Some optimal inapproximability results'',
Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, 1-10.
(MINIMUM VERTEX COVER, MINIMUM EDGE DELETION K-PARTITION, MAXIMUM CUT, MAXIMUM DIRECTED CUT, MAXIMUM SATISFYING LINEAR SUBSYSTEM, MAXIMUM K-SATISFIABILITY)

227
Håstad, J., Phillips, S., and Safra, S. (1993),
``A well-characterized approximation problem'',
Inform. Process. Lett. 47, 301-305.
(MAXIMUM SATISFIABILITY OF QUADRATIC EQUATIONS OVER GF[Q])

228
Hein, J., Jiang, T., Wang, L., and Zhang, K. (1996),
``On the complexity of comparing evolutionary trees'',
Disc. Appl. Math. 71, 153-169.
(MINIMUM PHYLOGENETIC TREE DISTANCE)

229
Hochbaum, D. S. (1982a),
``Approximation algorithms for the set covering and vertex cover problems'',
SIAM J. Comp. 11, 555-556.
(MINIMUM VERTEX COVER, MINIMUM SET COVER)

230
Hochbaum, D. S. (1982b),
``Heuristics for the fixed cost median problem'',
Math. Programming 22, 148-162.
(MINIMUM FACILITY LOCATION)

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

232
Hochbaum, D. S. (1997),
``Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems'', in
Approximation algorithms for NP-hard problems, PWS Publishing Company, Boston, 94-143.
(MINIMUM SET COVER)

233
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.
(MINIMUM K-CENTER)

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

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

236
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.
(MINIMUM 0-1 PROGRAMMING)

237
Hochbaum, D. S., and Shmoys, D. B. (1986),
``A unified approach to approximation algorithms for bottleneck problems'',
J. ACM 33, 533-550.
(MINIMUM METRIC BOTTLENECK WANDERING SALESPERSON PROBLEM, MINIMUM K-CENTER, MINIMUM K-CLUSTERING, MINIMUM K-SUPPLIER, MINIMUM K-SWITCHING NETWORK)

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

239
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.
(MINIMUM MULTIPROCESSOR SCHEDULING WITH SPEED FACTORS)

240
Hofmeister, T., and Lefmann, H. (1998),
``Approximating maximum independent sets in uniform hypergraphs'',
Proc. 23rd International Symp. on Mathematical Foundations of Comput. Sci., Lecture Notes in Comput. Sci. 1450, Springer-Verlag, 562-570.
(MINIMUM GRAPH COLORING)

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

242
Hoogeveen, J. A. (1978),
``Analysis of Christofides' heuristic: Some paths are more difficult than cycles'',
Oper. Res. Lett. 10, 178-193.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

243
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.
(MINIMUM PRECEDENCE CONSTRAINED SCHEDULING)

244
Horowitz, E., and Sahni, S. K. (1976),
``Exact and approximate algorithms for scheduling nonidentical processors'',
J. ACM 23, 317-327.
(MINIMUM MULTIPROCESSOR SCHEDULING, MINIMUM MULTIPROCESSOR SCHEDULING WITH SPEED FACTORS)

245
Horowitz, E., and Sahni, S. K. (1978),
Fundamentals of Computer Algorithms,
Pitman, London.
(MINIMUM GRAPH COLORING)

246
Hougardy, S., and Prömel, H. J. (1999),
``A 1.598 approximation algorithm for the steiner problem in graphs'',
Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 448-453.
http://www.informatik.hu-berlin.de/ hougardy/paper.html
(MINIMUM STEINER TREE)

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

248
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.
(MAXIMUM K-COLORABLE INDUCED SUBGRAPH)

249
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.
(MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM EDGE DOMINATING SET, MAXIMUM TRIANGLE PACKING, MAXIMUM H-MATCHING, MAXIMUM INDEPENDENT SET)

250
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.
(MAXIMUM TRIANGLE PACKING, MAXIMUM H-MATCHING, MAXIMUM 3-DIMENSIONAL MATCHING, MAXIMUM SET PACKING)

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

252
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.
(MINIMUM STEINER TREE)

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

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

255
Jansen, K. (1997),
``Approximation results for the optimum cost chromatic partition problem'',
Proc. 24th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1256, Springer-Verlag, 727-737.
(MINIMUM COLOR SUM)

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

257
Jiang, T., Kearney, P., and Li, M. (1998),
``Orchestrating quartets: approximation and data correction'',
Proc. 39th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 416-425.
(MINIMUM TREE ALIGNMENT)

258
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.
(MINIMUM STEINER TREE, MINIMUM TREE ALIGNMENT)

259
Jiang, T., and Li, M. (1994a),
``Approximating shortest superstrings with constraints'',
Theoretical Comput. Sci. 134, 473-491.
(SHORTEST COMMON SUPERSTRING)

260
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.
(SHORTEST COMMON SUPERSEQUENCE, LONGEST COMMON SUBSEQUENCE)

261
Johnson, D. S. (1974),
``Approximation algorithms for combinatorial problems'',
J. Comput. System Sci. 9, 256-278.
(MINIMUM DOMINATING SET, MINIMUM SET COVER, MINIMUM EXACT COVER, MAXIMUM K-SATISFIABILITY)

262
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.

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

264
Jonsson, P. (1997),
``Near-optimal nonapproximability results for some NPO PB-complete problems'',
Inform. Process. Lett. 68, 249-253.
http://www.ep.liu.se/ea/cis/1997/004/
(MAXIMUM BOUNDED 0-1 PROGRAMMING, MAXIMUM DISTINGUISHED ONES, MINIMUM DISTINGUISHED ONES)

265
Kann, V. (1991),
``Maximum bounded 3-dimensional matching is MAX SNP-complete'',
Inform. Process. Lett. 37, 27-35.
(MAXIMUM TRIANGLE PACKING, MAXIMUM 3-DIMENSIONAL MATCHING, MAXIMUM SET PACKING)

266
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.
(MAXIMUM COMMON SUBGRAPH, MAXIMUM COMMON INDUCED SUBGRAPH)

267
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.
(MINIMUM DOMINATING SET, MINIMUM INDEPENDENT DOMINATING SET, MINIMUM FEEDBACK VERTEX SET, MINIMUM FEEDBACK ARC SET, MAXIMUM COMMON SUBGRAPH, MINIMUM TEST COLLECTION, MAXIMUM DISTINGUISHED ONES, MAXIMUM NUMBER OF SATISFIABLE FORMULAS)

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

269
Kann, V. (1994b),
``Polynomially bounded minimization problems that are hard to approximate'',
Nordic J. Comp. 1, 317-331.
(MINIMUM INDEPENDENT DOMINATING SET, SHORTEST PATH WITH FORBIDDEN PAIRS, MINIMUM 0-1 PROGRAMMING, MINIMUM DISTINGUISHED ONES, MINIMUM NUMBER OF SATISFIABLE FORMULAS, SHORTEST COMPUTATION)

270
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.
(MAXIMUM INDUCED CONNECTED SUBGRAPH WITH PROPERTY P, MAXIMUM BOUNDED 0-1 PROGRAMMING, MINIMUM RELEVANT VARIABLES IN LINEAR SYSTEM)

271
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 , 2.
http://www.cs.uchicago.edu/publications/cjtcs/
(MINIMUM EDGE DELETION K-PARTITION, MAXIMUM K-CUT)

272
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.
(MAXIMUM SET SPLITTING, MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY)

273
Kant, G., and Bodlaender, H. L. (1997),
``Triangulating planar graphs while minimizing the maximum degree'',
Inform. and Comput. 135, 1-14.
(MINIMUM LENGTH TRIANGULATION)

274
Karger, D., Motwani, R., and Ramkumar, G. D. S. (1997),
``On approximating the longest path in a graph'',
Algorithmica 18, 82-98.
(LONGEST PATH)

275
Karger, D., Motwani, R., and Sudan, M. (1998),
``Approximate graph coloring by semidefinite programming'',
J. ACM 45, 246-265.
(MINIMUM GRAPH COLORING, MAXIMUM INDEPENDENT SET)

276
Karloff, H., and Zwick, U. (1997),
``A 7/8-approximation for MAX 3SAT?'',
Proc. 38th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 406-415.
(MAXIMUM K-SATISFIABILITY)

277
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.
(MINIMUM BIN PACKING)

278
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.
(MINIMUM PLANAR RECORD PACKING)

279
Karpinski, M. (1997),
``Polynomial time approximation schemes for some dense instances of NP-hard optimization problems'',
Proc. 1st Symp. on Randomization and Approximation Techniques in Comput. Sci., Lecture Notes in Comput. Sci. 1269, Springer-Verlag, 1-14.
(MINIMUM VERTEX COVER, MINIMUM STEINER TREE, MINIMUM SET COVER)

280
Karpinski, M., and Wirtgen, J. (1997),
``On approximation hardness of the bandwidth problem'',
Technical Report TR 97-041, ECCC.
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1997/TR97-041/index.html
(MINIMUM BANDWIDTH)

281
Karpinski, M., Wirtgen, J., and Zelikovsky, A. (1997),
``An approximation algorithm for the bandwidth problem on dense graphs'',
Technical Report TR97-017, ECCC.
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1997/TR97-004/index.html
(MINIMUM BANDWIDTH, MINIMUM DIRECTED BANDWIDTH)

282
Karpinski, M., and Zelikovsky, A. (1997),
``Approximating dense cases of covering problems'',
Technical Report TR97-004, ECCC.
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1997/TR97-004/index.html
(MINIMUM VERTEX COVER, MINIMUM STEINER TREE, MINIMUM SET COVER)

283
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.
(MINIMUM VEHICLE SCHEDULING ON TREE)

284
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.
(MAXIMUM HORN CORE)

285
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.
(MINIMUM PARALLEL PROCESSOR TOTAL FLOW TIME)

286
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.
(MINIMUM HEIGHT TWO DIMENSIONAL PACKING)

287
Khanna, S. (1997),
``A polynomial time approximation scheme for the SONET ring loading problem'',
Bell Labs Technical J. Spring, 36-41.
http://cm.bell-labs.com/who/sanjeev
(MINIMUM RING LOADING)

288
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.
(MINIMUM GRAPH COLORING)

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

290
Khanna, S., Motwani, R., Sudan, M., and Vazirani, U. (1999),
``On syntactic versus computational views of approximability'',
SIAM J. Comp. 28, 164-191.
(MINIMUM DOMINATING SET, MINIMUM SET COVER)

291
Khanna, S., Muthukrishnan, S., and Paterson, M. (1998),
``On approximating rectangle tiling and packing'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 384-393.
(MINIMUM RECTANGLE TILING)

292
Khanna, S., Muthukrishnan, S., and Skiena, S. (1997),
``Efficient array partitioning'',
Proc. 24th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1256, Springer-Verlag, 616-626.
(MINIMUM ARRAY PARTITION)

293
Khuller, S. (1997),
``Approximation algorithms for finding highly connected subgraphs'', in
Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, 236-265.
(MINIMUM BICONNECTIVITY AUGMENTATION)

294
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.
(MINIMUM K-CENTER)

295
Khuller, S., and Raghavachari, B. (1996),
``Improved approximation algorithms for uniform connectivity problems'',
J. Algorithms 21, 434-450.
(MINIMUM K-VERTEX CONNECTED SUBGRAPH, MINIMUM K-EDGE CONNECTED SUBGRAPH)

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

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

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

299
Khuller, S., Raghavachari, B., and Young, N. (1996a),
``Low degree spanning trees of small weight'',
SIAM J. Comp. 25, 355-368.
(MINIMUM GEOMETRIC 3-DEGREE SPANNING TREE)

300
Khuller, S., Raghavachari, B., and Young, N. (1996b),
``On strongly connected digraphs with bounded cycle length'',
Disc. Appl. Math. 69, 281-289.
(MINIMUM K-VERTEX CONNECTED SUBGRAPH, MINIMUM K-EDGE CONNECTED SUBGRAPH, MINIMUM STRONG CONNECTIVITY AUGMENTATION)

301
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.
(MINIMUM K-CENTER)

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

303
Khuller, S., and Vishkin, U. (1994),
``Biconnectivity approximations and graph carvings'',
J. ACM 41, 214-235.
(MINIMUM GENERALIZED STEINER NETWORK, MINIMUM K-EDGE CONNECTED SUBGRAPH)

304
Kim, S., and McNaughton, R. (1993),
``Computing the order of a locally testable automaton'',
Unpublished manuscript.
(MINIMUM LOCALLY TESTABLE AUTOMATON ORDER)

305
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.
(MINIMUM CHORDAL GRAPH COMPLETION, MINIMUM REGISTER SUFFICIENCY)

306
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.
(MINIMUM RATIO-CUT)

307
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.
(MAXIMUM DISJOINT CONNECTING PATHS)

308
Kleinberg, J. M. (1996),
``Single-source unsplittable flow'',
Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 68-77.
(MINIMUM UNSPLITTABLE FLOW)

309
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.
(MINIMUM BANDWIDTH)

310
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.
(MINIMUM K-CENTER)

311
Kohli, R., Krishnamurti, R., and Mirchandani, P. (1994),
``The minimum satisfiability problem'',
SIAM J. Disc. Math. 7, 275-283.
(MAXIMUM K-SATISFIABILITY, MINIMUM K-SATISFIABILITY)

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

313
Kolaitis, P. G., and Thakur, M. N. (1995),
``Approximation properties of NP minimization classes'',
J. Comput. System Sci. 50, 391-411.
(MINIMUM VERTEX DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P, MINIMUM EDGE DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P)

314
Kolliopoulos, S. G., and Stein, C. (1997),
``Improved approximation algorithms for unsplittable flow problems'',
Proc. 38th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 426-435.
(MINIMUM UNSPLITTABLE FLOW)

315
Kortsarz, G. (1998),
``On the hardness of approximating spanners'',
Proc. 1st Int. Workshop on Approximation Algorithms for Combinatorial Problems, , Lecture Notes in Comput. Sci., Springer-Verlag, 135-146.
(MINIMUM EDGE 2-SPANNER)

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

317
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.
(MAXIMUM EDGE SUBGRAPH)

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

319
Kortsarz, G., and Peleg, D. (1995),
``Approximation algorithms for minimum time broadcast'',
SIAM J. Disc. Math. 8, 401-427.
(MINIMUM BROADCAST TIME)

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

321
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.
(MINIMUM TRAVELING SALESPERSON)

322
Kou, L. T., Stockmeyer, L. J., and Wong, C. K. (1978),
``Covering edges by cliques with regard to keyword conflicts and intersection graphs'',
Commun. ACM 21, 135-139.
(MINIMUM CLIQUE COVER)

323
Koutsoupias, E., Papadimitriou, C. H., and Yannakakis, M. (1996),
``Searching a fixed graph'',
Proc. 23rd Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1099, Springer-Verlag, 280-289.
(MINIMUM TRAVELING REPAIRMAN)

324
Krivelevich, M., and Sudakov, B. (1998),
``Approximate coloring of uniform hypergraphs'',
Proc. 6th Ann. European Symp. on Algorithms, , Lecture Notes in Comput. Sci., Springer-Verlag, 477-489.
(MINIMUM GRAPH COLORING)

325
Krumke, S. O. (1995),
``On a generalization of the p-center problem'',
Inform. Process. Lett. 56, 67-71.
(MINIMUM K-CENTER)

326
Krumke, S. O., Marathe, M. V., Noltemeier, H., Ravi, R., Ravi, S. S., Sundaram, R., and Wirth, H. C. (1997),
``Improving spanning trees by upgrading nodes'',
Proc. 24th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1256, Springer-Verlag, 281-291.
http://www.zib.de/krumke/publications
(MINIMUM UPGRADING SPANNING TREE)

327
Kumar, V. (1998),
``Approximating circular arc colouring and bandwidth allocation in all-optical ring networks'',
Proc. 1st Int. Workshop on Approximation Algorithms for Combinatorial Problems, , Lecture Notes in Comput. Sci., Springer-Verlag, 147-158.
(MINIMUM GRAPH COLORING)

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

329
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.
(MINIMUM QUOTIENT CUT)

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

331
Lenstra, J. K., and Shmoys, D. B. (1995),
``Computing near-optimal schedules'', in
Scheduling Theory and its Applications, Wiley, Chichester, to appear.
(MINIMUM OPEN-SHOP SCHEDULING)

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

333
Leonardi, S., and Raz, D. (1997),
``Approximating total flow time on parallel machines'',
Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, 110-119.
(MINIMUM PARALLEL PROCESSOR TOTAL FLOW TIME)

334
Leung, J. Y.-T., and Wei, W.-D. (1995),
``Tighter bounds on a heuristic for a partition problem'',
Inform. Process. Lett. 56, 51-57.
(MINIMUM SUM OF SQUARES)

335
Levcopoulos, C., and Gudmundsson, J. (1997),
``Approximation algorithms for covering polygons with squares and similar problems'',
Proc. 1st Symp. on Randomization and Approximation Techniques in Comput. Sci., Lecture Notes in Comput. Sci. 1269, Springer-Verlag, 27-31.
(MINIMUM RECTANGLE COVER)

336
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.
(MINIMUM MAXIMUM DISJOINT CONNECTING PATHS)

337
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.
(MINIMUM BOUNDED DIAMETER AUGMENTATION)

338
Li, K., and Cheng, K. (1990),
``On three-dimensional packing'',
SIAM J. Comp. 19, 847-867.
(MINIMUM HEIGHT TWO DIMENSIONAL PACKING)

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

340
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.
(MINIMUM GRAPH TRANSFORMATION)

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

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

343
Lu, H., and Ravi, R. (1992),
``The power of local optimization: Approximation algorithms for maximum-leaf spanning tree'',
Proc. 30th Ann. Allerton Conf. on Communication, Control and Computing, , 533-542.
(MAXIMUM LEAF SPANNING TREE)

344
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.
(MINIMUM RESOURCE CONSTRAINED SCHEDULING)

345
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.
(MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P, MINIMUM VERTEX DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P, MAXIMUM INDUCED CONNECTED SUBGRAPH WITH PROPERTY P)

346
Lund, C., and Yannakakis, M. (1994),
``On the hardness of approximating minimization problems'',
J. ACM 41, 960-981.
(MINIMUM GRAPH COLORING, MINIMUM CLIQUE PARTITION, MINIMUM COMPLETE BIPARTITE SUBGRAPH COVER, MINIMUM EXACT COVER, MINIMUM BIN PACKING)

347
Mahajan, S., and Ramesh, J. (1995),
``Derandomizing semidefinite programming based approximation algorithms'',
Proc. 36th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 162-169.
(MINIMUM GRAPH COLORING, MAXIMUM CLIQUE, MAXIMUM K-COLORABLE SUBGRAPH, MAXIMUM CUT, MAXIMUM K-CUT)

348
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.
(MINIMUM QUOTIENT CUT)

349
Malesinska, E., and Panconesi, A. (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, Springer-Verlag, 308-322.
(MAXIMUM FREQUENCY ALLOCATION)

350
Marathe, M. V., Breu, H., Hunt III, H. B., Ravi, S. S., and Rosenkrantz, D. J. (1995),
``Simple heuristics for unit disk graphs'',
Networks 25, 59-68.
(MINIMUM INDEPENDENT DOMINATING SET, MINIMUM GRAPH COLORING)

351
Marathe, M. V., Hunt III, H. B., and Ravi, S. S. (1996),
``Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs'',
Disc. Appl. Math. 64, 135-149.
(MINIMUM DOMINATING SET)

352
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.
(MINIMUM BROADCAST TIME)

353
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.
(MINIMUM GRAPH INFERENCE)

354
Mata, C. S., and Mitchell, J. S. B. (1995),
``Approximation algorithms for geometric tour and network design problems'',
Proc. 11th Ann. ACM Symp. Comput. Geom., ACM, 360-369.
(MINIMUM GEOMETRIC TRAVELING SALESPERSON, MINIMUM TRAVEL ROBOT LOCALIZATION, MINIMUM RED-BLUE SEPARATION)

355
Michel, C., Schroeter, H., and Srivastav, A. (1995),
``TSP and matching in printed circuit board assembly'',
European Symposium on Operations Research, , .
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

356
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.
(SHORTEST COMMON SUPERSEQUENCE)

357
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.
(MINIMUM K-LINK PATH IN A POLYGON)

358
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.
(MINIMUM SEPARATING SUBDIVISION)

359
Möhring, R. H., Schäffter, M. W., and Schulz, A. S. (1996),
``Scheduling jobs with communication delays: using infeasible solutions for approximation'',
Proc. 4th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1136, Springer-Verlag, 76-90.
(MINIMUM PRECEDENCE CONSTRAINED SCHEDULING)

360
Monien, B., and Speckenmeyer, E. (1985),
``Ramsey numbers and an approximation algorithm for the vertex cover problem'',
Acta Inf. 22, 115-123.
(MINIMUM VERTEX COVER)

361
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.
(MINIMUM CUT COVER)

362
Naor, J., and Zosin, L. (1997),
``A 2-approximation algorithm for the directed multiway cut problem'',
Proc. 38th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 548-553.
(MINIMUM MULTIWAY CUT)

363
Natanzon, A., Shamir, R., and Sharan, R. (1998),
``A polynomial approximation algorithm for the minimum fill-in problem'',
Proc. 30th Ann. ACM Symp. on Theory of Comp., ACM, 41-47.
(MINIMUM CHORDAL GRAPH COMPLETION)

364
Nayak, A., Sinclair, A., and Zwick, U. (1998),
``Spatial codes and the hardness of string folding problems'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 639-648.
(MAXIMUM STRING FOLDING)

365
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.
(MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P, MAXIMUM 3-DIMENSIONAL MATCHING)

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

367
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.
(MINIMUM TRAVELING SALESPERSON, MINIMUM 0-1 PROGRAMMING, MINIMUM DISTINGUISHED ONES)

368
Panconesi, A., and Ranjan, D. (1993),
``Quantifiers and approximation'',
Theoretical Comput. Sci. 107, 145-163.
(MAXIMUM K-COLORABLE INDUCED SUBGRAPH, MAXIMUM DISTINGUISHED ONES)

369
Papadimitriou, C. H. (1985),
``An algorithm for shortest-path motion in three dimensions'',
Inform. Process. Lett. 20, 259-263.
(SHORTEST PATH MOTION IN 3 DIMENSIONS)

370
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.
(MINIMUM GRAPH MOTION PLANNING)

371
Papadimitriou, C. H., and Yannakakis, M. (1991),
``Optimization, approximation, and complexity classes'',
J. Comput. System Sci. 43, 425-440.
(MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM FEEDBACK ARC SET, MAXIMUM INDEPENDENT SET, MAXIMUM K-COLORABLE SUBGRAPH, MAXIMUM CUT, MAXIMUM DIRECTED CUT, MINIMUM SET COVER, MAXIMUM SATISFIABILITY, MAXIMUM K-SATISFIABILITY, MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY)

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

373
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.
(MINIMUM QUOTIENT CUT)

374
Paz, A., and Moran, S. (1981),
``Non deterministic polynomial optimization problems and their approximations'',
Theoretical Comput. Sci. 15, 251-277.
(MINIMUM CLIQUE PARTITION)

375
Peleg, D., and Reshef, E. (1998),
``Deterministic polylog approximation for minimum communication spanning trees'',
Proc. 25th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1443, Springer-Verlag, 670-679.
(MINIMUM COMMUNICATION COST SPANNING TREE)

376
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.
(MINIMUM SET COVER)

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

378
Petrank, E. (1994),
``The hardness of approximation: gap location'',
Computational Complexity 4, 133-157.
(MINIMUM VERTEX COVER, MINIMUM EDGE COLORING, MAXIMUM SET SPLITTING)

379
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.
(MINIMUM WEIGHTED COMPLETION TIME SCHEDULING)

380
Phillips, C. A. (1993),
``The network inhibition problem'',
Proc. 25th Ann. ACM Symp. on Theory of Comp., ACM, 776-785.
(MINIMUM NETWORK INHIBITION ON PLANAR GRAPHS, SHORTEST WEIGHT-CONSTRAINED PATH)

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

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

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

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

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

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

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

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

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

390
Queyranne, M. (1986),
``Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems'',
Oper. Res. Lett. 4, 231-234.
(MINIMUM QUADRATIC 0-1 ASSIGNMENT)

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

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

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

394
Rao, S., and Richa, A. W. (1998),
``New approximation techniques for some ordering problems'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 211-218.
(MINIMUM INTERVAL GRAPH COMPLETION, MINIMUM LINEAR ARRANGEMENT, MINIMUM STORAGE-TIME SEQUENCING)

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

396
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.
(MINIMUM BROADCAST TIME)

397
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.
(MINIMUM K-SPANNING TREE)

398
Ravi, R., and Williamson, D. (1997),
``An approximation algorithm for minimum-cost vertex-connectivity problems'',
Algorithmica 18, 21-43.
(MINIMUM K-VERTEX CONNECTED SUBGRAPH)

399
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.
(MAXIMUM K-FACILITY DISPERSION)

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

401
Raz, R., and Safra, S. (1997),
``A sub-constant error-probability low-degree test, and sub-constant error-probability pcp characterization of np'',
Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, 475-484.
(MINIMUM DOMINATING SET, MINIMUM SET COVER)

402
S. Nicoloso, X. Song, M. Sarrafzadeh (1994),
,
Technical Report R. 390, Istituto di Analisi dei Sistemi ed Informatica (IASI-CNR).
(MINIMUM COLOR SUM)

403
Sahni, S. K., and Gonzalez, T. F. (1976),
``P-complete approximation problems'',
J. ACM 23, 555-565.
(MINIMUM VERTEX DISJOINT CYCLE COVER, MINIMUM EDGE DISJOINT CYCLE COVER, MINIMUM EDGE DELETION K-PARTITION, MINIMUM K-CLUSTERING SUM, MINIMUM GENERALIZED 0-1 ASSIGNMENT, MINIMUM QUADRATIC 0-1 ASSIGNMENT)

404
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.
(MINIMUM SINGLE-SINK EDGE INSTALLATION)

405
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.
(MINIMUM K-CUT)

406
Savage, Carla (1982),
``Depth-first search and the vertex cover problem'',
Inform. Process. Lett. 14, 233-237.
(MINIMUM VERTEX COVER)

407
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.
(MINIMUM HEIGHT TWO DIMENSIONAL PACKING)

408
Schulz, A. S., and Skutella, M. (1996),
``Scheduling-LPs bear probabilities: Randomized approximations for Min-sum criteria'',
Technical Report 533/1996, Technical University of Berlin, Department of Mathematics.
(MINIMUM SEQUENCING WITH RELEASE TIMES)

409
Schulz, A. S., and Skutella, M. (1997a),
``Scheduling-LPs bear probabilities: randomized approximation for Min-sum criteria'',
Proc. 5th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1284, Springer-Verlag, 416-429.
(MINIMUM WEIGHTED COMPLETION TIME SCHEDULING)

410
Schulz, A. S., and Skutella, M. (1997b),
``Random-based scheduling: New approximations and LP lower bounds'',
Proc. 1st Symp. on Randomization and Approximation Techniques in Comput. Sci., Lecture Notes in Comput. Sci. 1269, Springer-Verlag, 119-133.
(MINIMUM SEQUENCING WITH RELEASE TIMES, MINIMUM WEIGHTED COMPLETION TIME SCHEDULING)

411
Serdyukov, A. I. (1984),
``An algorithm with an estimate for the traveling salesman problem of the maximum'',
Upravlyaemye Sistemy 25, 80-86.
(MINIMUM TRAVELING SALESPERSON)

412
Seymour, P. D. (1995),
``Packing directed circuits fractionally'',
Combinatorica 15, 281-288.
(MINIMUM FEEDBACK VERTEX SET)

413
Seymour, P. D., and Thomas, R. (1994),
``Call routing and the rat catcher'',
Combinatorica 14, 217-241.
(MINIMUM ROUTING TREE CONGESTION)

414
Shachnai, H., and Tamir, T. (1998),
``Noah's bagels - some combinatorial aspects'',
Proc. 1st Int. Conf. on Fun with Algorithms, , .
http://www.cs.technion.ac.il/ hadas/
(MAXIMUM CLASS-CONSTRAINED KNAPSACK)

415
Shamir, R., and Tsur, D. (1998),
``The maximum subforest problem: Approximation and exact algorithms'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 394-399.
(MAXIMUM SUBFOREST)

416
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.
(MINIMUM B-BALANCED CUT)

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

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

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

420
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.
(MAXIMUM CHANNEL ASSIGNMENT)

421
Simon, H. U. (1990),
``On approximate solutions for combinatorial optimization problems'',
SIAM J. Disc. Math. 3, 294-310.
(MINIMUM CLIQUE COVER, MINIMUM COMPLETE BIPARTITE SUBGRAPH COVER, MINIMUM CONSISTENT FINITE AUTOMATON)

422
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.
(MINIMUM TIME-COST TRADEOFF)

423
Srinivasan, A. (1995),
``Improved approximations of packing and covering problems'',
Proc. 27th Ann. ACM Symp. on Theory of Comp., ACM, 268-276.
(MINIMUM SET COVER, MAXIMUM PACKING INTEGER PROGRAMMING, MINIMUM COVERING INTEGER PROGRAMMING)

424
Srinivasan, A. (1997),
``Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems'',
Proc. 38th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 416-425.
(MAXIMUM DISJOINT CONNECTING PATHS)

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

426
Tamir, A. (1991),
``Obnoxious facility location on graphs'',
SIAM J. Disc. Math. 4, 550-567.
(MAXIMUM K-FACILITY DISPERSION)

427
Tarhio, J., and Ukkonen, E. (1988),
``A greedy approximation algorithm for constructing shortest common superstrings'',
Theoretical Comput. Sci. 57, 131-145.
(SHORTEST COMMON SUPERSTRING)

428
Trevisan, L. (1996),
``Positive linear programming, parallel approximation and PCPs'',
Proc. 4th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1136, Springer-Verlag, 62-75.
(MAXIMUM K-CONSTRAINT SATISFACTION)

429
Trevisan, L. (1997),
``When Hamming meets Euclid: the approximability of geometric TSP and MST'',
Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, 21-29.
(MINIMUM GEOMETRIC TRAVELING SALESPERSON)

430
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.
(MAXIMUM K-SATISFIABILITY)

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

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

433
Verbitsky, O. (1994),
``On the largest common subgraph problem'',
Unpublished manuscript.
(MAXIMUM COMMON SUBGRAPH)

434
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.
(MAXIMUM H-MATCHING, MAXIMUM INDEPENDENT SET, MAXIMUM K-CONSTRAINT SATISFACTION)

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

436
Vishwanathan, S. (1996),
``An $o(\log^*n)$ approximation algorithm for the asymmetric p-center problem'',
Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 1-5.
(MINIMUM K-CENTER)

437
Vishwanathan, Sundar (1996),
``Personal communication'',
Unpublished manuscript.
(MAXIMUM INDEPENDENT SET)

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

439
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.
(MAXIMUM MAP LABELING)

440
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.
(MINIMUM K-SUPPLIER)

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

442
Williamson, D. P., Goemans, M. X., Mihail, M., and Vazirani, V. V. (1995),
``A primal-dual approximation algorithm for generalized Steiner network problems'',
Combinatorica 15, 435-454.
(MINIMUM GENERALIZED STEINER NETWORK)

443
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.
(MINIMUM OPEN-SHOP SCHEDULING, MINIMUM FLOW-SHOP SCHEDULING, MINIMUM JOB SHOP SCHEDULING)

444
Wöginger, G. J., and Yu, Z. (1992),
``A heuristic for preemptive scheduling with set-up times'',
Computing 49, 151-158.
(MINIMUM PREEMPTIVE SCHEDULING WITH SET-UP TIMES)

445
Wu, B. Y., Chao, K., and Tang, C. Y. (1998),
``Exact and approximation algorithms for constructing ultrametric trees from distance metrics'',
Proc. 4th Ann. Int. Conf. on Computing and Combinatorics, Lecture Notes in Comput. Sci. 1449, Springer-Verlag, 299-308.
(MINIMUM SIZE ULTRAMETRIC TREE)

446
Wu, B. Y., Lancia, G., Bafna, V., Chao, K., Ravi, R., and Tang, C. Y. (1998),
``A polynomial time approximation scheme for Minimum routing cost spanning tree'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 21-32.
(MINIMUM COMMUNICATION COST SPANNING TREE, MINIMUM TREE ALIGNMENT)

447
Yannakakis, M. (1979),
``The effect of a connectivity requirement on the complexity of maximum subgraph problems'',
J. ACM 26, 618-630.
(MINIMUM VERTEX DELETION TO OBTAIN CONNECTED SUBGRAPH WITH PROPERTY P)

448
Yannakakis, M., and Gavril, F. (1980),
``Edge dominating sets in graphs'',
SIAM J. Appl. Math. 38, 364-372.
(MINIMUM MAXIMAL MATCHING)

449
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.
(MINIMUM MULTI-CUT)

450
Yue, M. (1991),
``A simple proof of the inequality $MFFD(L)\le
\frac{71}{60}OPT(L)+\frac{78}{71}, \forall L$ for the MFFD bin-pack algorithm'',
Technical Report RRR # 20-91, Rutcor, Rutgers Center for Operations Research, Rutgers University, New Jersey.
(MINIMUM BIN PACKING)

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

452
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.
(MINIMUM VERTEX COVER, MINIMUM GRAPH COLORING, MINIMUM FEEDBACK VERTEX SET, MINIMUM FEEDBACK ARC SET, MINIMUM CLIQUE COVER, MINIMUM STEINER TREE, MAXIMUM K-CUT, MAXIMUM 3-DIMENSIONAL MATCHING, MINIMUM SET COVER, MINIMUM HITTING SET, MAXIMUM CONSTRAINED PARTITION, MAXIMUM CONSTRAINED SEQUENCING TO MINIMIZE TARDY TASK WEIGHT)

453
Zwick, U. (1998),
``Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint'',
Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 201.
(MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY, MAXIMUM K-CONSTRAINT SATISFACTION)



Viggo Kann
1999-04-22