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)