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., 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)

14
Alon, Noga, and Kahale, Nabil (1998),
``Approximating the independence number via the $\theta$ functio n'',
Math. Programming 80, 253-264.
(MAXIMUM CLIQUE, MAXIMUM INDEPENDENT SET)

15
Althöfer, I., Das, G., Dobkin, D., and Joseph, D. (1990),
``Generating sparse spanners for weighted graphs'',
Proc. 2nd Scandinavian Workshop on Algorithm Theory, , Lecture Notes in Comput. Sci., Springer-Verlag, 26-37.
(MINIMUM EDGE K-SPANNER)

16
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])

17
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)

18
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)

19
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. 1563, Springer-Verlag, 237-247.
(MAXIMUM K-CUT)

20
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)

21
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)

22
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)

23
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)

24
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)

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

26
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)

27
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)

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

29
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)

30
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)

31
Arkin, E. M., and Hassin, R. (2000),
``Approximating the maximum quadratic assignment problem'',
Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, to appear.
(MAXIMUM QUADRATIC ASSIGNMENT)

32
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)

33
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)

34
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)

35
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)

36
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)

37
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)

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

39
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)

40
Arora, Sanjeev, Raghavan, Prabhakar, and Rao, Satish (1998),
``Approximation schemes for Euclidean k-medians and related problems'',
Proc. 30th Ann. ACM Symp. on Theory of Comp., ACM-SIAM, 106-113.
(MINIMUM K-MEDIAN)

41
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)

42
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)

43
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)

44
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)

45
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)

46
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)

47
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)

48
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)

49
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)

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

51
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)

52
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)

53
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)

54
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)

55
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)

56
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)

57
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)

58
Bar-Noy, A., Halldórsson, M. M., Kortsarz, G., Shachnai, H., and Salman, R. (1999),
``Sum multicoloring of graphs'',
Proc. 7th Ann. European Symp. on Algorithms, , Lecture Notes in Comput. Sci., Springer-Verlag, .
(MINIMUM COLOR SUM)

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

60
Bar-Yehuda, R. (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)

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

62
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)

63
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)

64
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)

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

66
Bazgan, C., and Fernandez de la Vega, W. (1999),
``A polynomial time approximation scheme for dense Min2SAT'',
Proc. 12th Int. Symp. on Fundamentals of Computation Theory, Lecture Notes in Comput. Sci. 1684, Springer-Verlag, 91-99.
(MINIMUM K-SATISFIABILITY, MINIMUM EQUIVALENCE DELETION)

67
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)

68
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, LONGEST COMMON SUBSEQUENCE, MAXIMUM COMPATIBLE BINARY CONSTRAINT SATISFACTION)

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

70
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)

71
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)

72
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)

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

74
Berman, P., and DasGupta, B. (1997),
``Complexities of efficient solutions of rectilinear polygon cover problems'',
Algorithmica 17, 331-356.
(MINIMUM RECTANGLE COVER)

75
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)

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

77
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)

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

79
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)

80
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)

81
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)

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

83
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)

84
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)

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

86
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)

87
Böckenhauer, H., Hromkovic, J., Klasing, R., Seibert, S., and Unger, W. (2000),
``An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inquality'',
Proc. 17th Ann. Symp. on Theoretical Aspects of Comput. Sci., Lecture Notes in Comput. Sci. 1770, Springer-Verlag, 382-394.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

88
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)

89
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)

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

91
Boros, E. (1999),
``Maximum renamable Horn sub-CNFs'',
Disc. Appl. Math. 96-97, 29-40.
(MAXIMUM RENAMABLE HORN SUBFORMULA)

92
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. 15nth Ann. Symp. on Theoretical Aspects of Comput. Sci., , Lecture Notes in Comput. Sci., Springer-Verlag, 298-308.
(MINIMUM VERTEX COVER)

93
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)

94
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)

95
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)

96
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)

97
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)

98
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)

99
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)

100
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)

101
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)

102
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)

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

104
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)

105
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)

106
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)

107
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)

108
Chen, Z.-Z. (1996),
``Practical approximation schemes for maximum induced-subgraph problems on $K_{3,3}$-free or $K_{5}$-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)

109
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)

110
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)

111
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)

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

113
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)

114
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)

115
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)

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

117
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)

118
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)

119
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)

120
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)

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

122
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)

123
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)

124
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)

125
Crescenzi, P., Kann, V., Silvestri, R., and Trevisan, L. (1999),
``Structure in approximation classes'',
SIAM J. Comp. 28, 1759-1782.
(MINIMUM EDGE COLORING, MINIMUM DEGREE SPANNING TREE, MINIMUM BIN PACKING)

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

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

128
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)

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

130
Czumaj, A., and Lingas, A. (1999),
``On approximability of the minimum-cost k-connected spanning subgraph problem'',
Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 281-290.
(MINIMUM K-EDGE CONNECTED SUBGRAPH)

131
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)

132
Damian-Iordache, M., and Pemmaraju, S. V. (1999),
``Hardness of approximating independent domination in circle graphs'',
Proc. 10th Ann. Int. Symp. on Algorithms and Computation, Lecture Notes in Comput. Sci. 1741, Springer-Verlag, 56-69.
(MINIMUM INDEPENDENT DOMINATING SET)

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

134
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)

135
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)

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

137
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)

138
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)

139
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)

140
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)

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

142
Elkin, M., and Peleg, D. (1999),
``The hardness of approximating spanner problems'',
Technical report, Weizmann Institute.
(MINIMUM EDGE K-SPANNER)

143
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.csc.kth.se/~enge/forskning-en.html
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM)

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

145
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)

146
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)

147
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)

148
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)

149
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)

150
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)

151
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)

152
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)

153
Feige, U. (1998),
``A threshold of $\ln n$ for approximating set cover'',
J. ACM 45, 634-652.
(MINIMUM DOMINATING SET, MINIMUM SET COVER, MAXIMUM K-SATISFIABILITY)

154
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)

155
Feige, U., Halldórsson, M. M., and Kortsarz, G. (2000),
``Approximating the domatic number'',
Proc. 32nd Ann. ACM Symp. on Theory of Comp., ACM, .
(MAXIMUM DOMATIC PARTITION)

156
Feige, U., and Kilian, J. (1998),
``Zero knowledge and the chromatic number'',
J. Comput. System Sci. 57, 187-199.
(MINIMUM GRAPH COLORING, MINIMUM COLOR SUM)

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

158
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)

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

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

161
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)

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

163
Fernandez de la Vega, W., and Karpinski, M. (1999),
``On the approximation hardness of dense TSP and other path problems'',
Inform. Process. Lett. 70, 53-55.
(MINIMUM METRIC TRAVELING SALESPERSON PROBLEM, LONGEST PATH)

164
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)

165
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)

166
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)

167
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)

168
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)

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

170
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)

171
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)

172
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)

173
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)

174
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)

175
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)

176
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 K-CUT)

177
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)

178
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)

179
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)

180
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)

181
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)

182
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)

183
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)

184
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)

185
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)

186
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)

187
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)

188
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)

189
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)

190
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)

191
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)

192
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)

193
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)

194
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)

195
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)

196
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)

197
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)

198
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)

199
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)

200
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)

201
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)

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

203
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)

204
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)

205
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)

206
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)

207
Gudmundsson, J., and Levcopoulos, C. (1999),
``Close approximation of minimum rectangular coverings'',
J. Combinatorial Optimization 3, 437-452.
(MINIMUM RECTANGLE COVER)

208
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)

209
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)

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

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

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

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

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

215
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)

216
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)

217
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)

218
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'',
J. Graph Algorithms and Applications 1, 1-13.
(MAXIMUM INDEPENDENT SET, MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P)

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

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

221
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)

222
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)

223
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)

224
Halldórsson, M. M. (1999a),
``Approximations of weighted independent set and hereditary subset problems'',
Proc. 5th Ann. Int. Conf. on Computing and Combinatorics, , Lecture Notes in Comput. Sci., Springer-Verlag, 261-270.
(MAXIMUM CLIQUE, MAXIMUM INDEPENDENT SET, MAXIMUM INDEPENDENT SEQUENCE, MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P, MAXIMUM SET PACKING)

225
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)

226
Halldórsson, M. M., and Kortsarz, G. (1999),
``Multicoloring planar graphs and partial k-trees'',
Proc. 2nd Int. Workshop on Approximation Algorithms for Combinatorial Problems, , Lecture Notes in Comput. Sci., Springer-Verlag, .
(MINIMUM COLOR SUM)

227
Halldórsson, M. M., Kortsarz, G., and Nutov, Z. (1999),
``Transforming a preemptive coloring into a non-preemptive one with applications'',
Unpublished manuscript.
(MINIMUM COLOR SUM)

228
Halldórsson, M. M., Kortsarz, G., Proskurowski, A., Salman, R., Shachnai, H., and Telle, J. A. (1999),
``Multi-coloring trees'',
Proc. 5th Ann. Int. Conf. on Computing and Combinatorics, , Lecture Notes in Comput. Sci., Springer-Verlag, 271-280.
(MINIMUM COLOR SUM)

229
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)

230
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)

231
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)

232
Halperin, E. (2000),
``Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs'',
Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, .
(MINIMUM VERTEX COVER)

233
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)

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

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

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

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

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

239
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)

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

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

242
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)

243
Håstad, J. (1999),
``Clique is hard to approximate within $n^{1-\varepsilon }$'',
Acta Mathematica 182, 105-142.
(MAXIMUM CLIQUE)

244
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])

245
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)

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

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

248
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)

249
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)

250
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)

251
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)

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

253
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)

254
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)

255
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)

256
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)

257
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)

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

259
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)

260
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)

261
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)

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

263
Hunt III, H. B., Marathe, M. V., Radhakrishnan, V., Ravi, S. S., Rosenkrantz, D. J., and Stearns, R. E. (1994),
``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)

264
Hunt III, H. B., Marathe, M. V., Radhakrishnan, V., Ravi, S. S., Rosenkrantz, D. J., and Stearns, R. E. (1998),
``Nc-approximation schemes for NP- and PSPACE-hard problems for geometric graphs'',
J. Algorithms 26, 238-274.
(MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM EDGE DOMINATING SET, MAXIMUM TRIANGLE PACKING, MAXIMUM H-MATCHING, MAXIMUM INDEPENDENT SET)

265
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)

266
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)

267
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)

268
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)

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

270
Jansen, K. (2000),
``Approximation results for the optimum cost chromatic partition problem'',
J. Algorithms 34, 54-89.
(MINIMUM COLOR SUM)

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

272
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)

273
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)

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

275
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)

276
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)

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

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

279
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)

280
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)

281
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)

282
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)

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

284
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)

285
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)

286
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)

287
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)

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

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

290
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)

291
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)

292
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)

293
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)

294
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)

295
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)

296
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)

297
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)

298
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)

299
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)

300
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)

301
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)

302
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)

303
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)

304
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)

305
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)

306
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)

307
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)

308
Khanna, S., Sudan, M., and Trevisan, L. (1997),
``Constraint satisfaction: the approximability of minimization problems'',
Proc. 12th Annual IEEE Conference on Computational Complexity, , 282-296.
(MAXIMUM K-CONSTRAINT SATISFACTION)

309
Khanna, S., Sudan, M., and Williamson, D. P. (1997),
``A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction'',
Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, 11-20.
(MAXIMUM K-CONSTRAINT SATISFACTION)

310
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)

311
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)

312
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)

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

314
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)

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

316
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)

317
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)

318
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)

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

320
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)

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

322
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)

323
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)

324
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)

325
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)

326
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)

327
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)

328
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)

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

330
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)

331
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)

332
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 K-SPANNER)

333
Kortsarz, G., and Peleg, D. (1994),
``Generating sparse 2-spanners'',
J. Algorithms 17, 222-236.
(MINIMUM EDGE K-SPANNER)

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

335
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)

336
Kortsarz, G., and Peleg, D. (1998),
``Generating low-degree 2-spanners'',
SIAM J. Comp. 27, 1438-1456.
(MINIMUM EDGE K-SPANNER)

337
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)

338
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)

339
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)

340
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)

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

342
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)

343
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)

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

345
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)

346
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)

347
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)

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

349
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)

350
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)

351
Levcopoulos, C. (1985),
``A fast heuristic for covering polygons by rectangles'',
Proc. Fundamentals of Computation Theory, Lecture Notes in Comput. Sci. 199, Springer-Verlag, .
(MINIMUM RECTANGLE COVER)

352
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)

353
Levcopoulos, C., and Krznaric, D. (1998),
``Quasi-greedy triangulations approximating the minimum weight triangulation'',
J. Algorithms 27, 303-338.
(MINIMUM LENGTH TRIANGULATION)

354
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)

355
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)

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

357
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)

358
Li, M., Ma, B., and Wang, L. (1999),
``Finding similar regions in many strings'',
Proc. 31st Ann. ACM Symp. on Theory of Comp., ACM-SIAM, 473-482.
http://math.uwaterloo.ca/ b3ma/pub/similar-region.ps.zip
(NEAREST STRING)

359
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)

360
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)

361
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)

362
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)

363
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)

364
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)

365
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)

366
Ma, B., and Wang, L. (1999),
``On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints'',
J. Comput. System Sci. , to appear.
http://math.uwaterloo.ca/ b3ma/pub/disjoint-path.ps.zip
(MAXIMUM DISJOINT CONNECTING PATHS)

367
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.
(MAXIMUM CLIQUE, MAXIMUM K-COLORABLE SUBGRAPH, MAXIMUM K-CUT)

368
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)

369
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)

370
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)

371
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.
(MAXIMUM DOMATIC PARTITION)

372
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)

373
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)

374
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)

375
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)

376
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)

377
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)

378
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)

379
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)

380
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)

381
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)

382
Nagamochi, H., and Ibaraki, T. (1999),
``An approximation of the minimum vertex cover in a graph'',
Japan J. Indust. Appl. Math. 16, 369-375.
(MINIMUM VERTEX COVER)

383
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)

384
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)

385
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)

386
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)

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

388
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)

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

390
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)

391
Papadimitriou, C. H. (1994),
Computational Complexity,
Addison-Wesley, Reading MA, .
(MAXIMUM K-SATISFIABILITY)

392
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)

393
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)

394
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)

395
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)

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

397
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)

398
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)

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

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

401
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)

402
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)

403
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)

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

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

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

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

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

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

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

411
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)

412
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)

413
Raghavachari, B., and Veerasamy, J. (1999),
``A 3/2-approximation algorithm for the mixed postman problem'',
SIAM J. Disc. Math. 12, 425-433.
(MINIMUM CHINESE POSTMAN FOR MIXED GRAPHS)

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

415
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)

416
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)

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

418
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)

419
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)

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

421
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)

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

423
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)

424
Robins, G., and Zelikovsky, A. (2000),
``Improved steiner tree approximation in graphs'',
Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 770-779.
(MINIMUM STEINER TREE)

425
S. Nicoloso, X. Song, M. Sarrafzadeh (1999),
``On the sum coloring problem on interval graphs'',
Algorithmica 23, 109-126.
(MINIMUM COLOR SUM)

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

427
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)

428
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)

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

430
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)

431
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)

432
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)

433
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)

434
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)

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

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

437
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)

438
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)

439
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)

440
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)

441
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)

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

443
Simon, H. U. (1989),
``Approximation algorithms for channel assignment in cellular radio networks'',
Proc. 7th Int. Symp. on Fundamentals of Computation Theory, Lecture Notes in Comput. Sci. 380, Springer-Verlag, 405-416.
(MAXIMUM CHANNEL ASSIGNMENT)

444
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)

445
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)

446
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)

447
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)

448
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)

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

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

451
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)

452
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)

453
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)

454
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)

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

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

457
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)

458
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)

459
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)

460
Vishwanathan, S. (1996),
``Personal communication'',
Unpublished manuscript.
(MAXIMUM INDEPENDENT SET)

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

462
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)

463
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)

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

465
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)

466
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)

467
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)

468
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)

469
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)

470
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)

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

472
Ye, Y. (1999),
``A .699 approximation algorithm for Max-Bisection'',
Math. Programming , to appear.
http://dollar.biz.uiowa.edu/col/ye/
(MAXIMUM CUT)

473
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)

474
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)

475
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)

476
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)

477
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
2000-04-23