Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP

ABSTRACT

Let G=(V, E) be an undirected graph where V and E are the sets of vertices and edges of G, respectively. A subset of the vertices S ⊆ V is independent if all of its members are pairwise nonadjacent, i.e., have no edge between them. A solution to the NP-hard maximum independent set problem is an independent set of maximum cardinality. This article describes gmis, a set of Fortran subroutines to find an approximate solution of a maximum independent set problem. A greedy randomized adaptive search procedure (GRASP) is used to produce the solutions. The algorithm is described in detail. Implementation and usage of the package is outlined, and computational experiments are reported, illustrating solution quality as a function of running time.

REFERENCES

• 1: ARORA, S., LUND, C., MOTWAN, R., SUDAN, M., AND SZEGEDY, M. 1992. Proof verification and hardness of approximation problems. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science. 14-23.
• 2: BOLLOBAS, B. 1985. Random Graphs. Academic Press.
• 3: CARRAGHAN, R., AND PARDALOS, P. 1990. An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9, 375-382.
• 4: FEO, T. A., AND RESENDE, M.G. 1995. Greedy randomized adaptive search procedures. J. Global Opt. 6, 109-133.
• 5: FEO, T. A., RESENDE, M. G., AND SMITH, S.H. 1994. A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42, 860-878.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: JOHNSON, D. S., AND TRICK, M. n., EDS. 1996. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. DIMACS Series on Discrete Mathematics and Theoretical Computer Science. Vol. 26. American Mathematical Society.
• 8: PARDALOS, P., PITSOULIS, L., AND RESENDE, M. 1995. A parallel GRASP implementation for the quadratic assignment problem. In Parallel Algorithms for Irregularly Structured Problems, A. Ferreira and J. Rolim, Eds. Kluwer Academic Publishers, 111-130.
• 9: PARDALOS, P., AND XUE, J. 1994. The maximum clique problem. J. Global Opt. 4 301-328.
• 10: Linus Schrage, A More Portable Fortran Random Number Generator, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.132-138, June 1979 [doi>10.1145/355826.355828]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Performance

Keywords:
Fortran subroutines, GRASP, combinatorial optimization, local search, maximum clique, maximum independent set