Two-phase greedy algorithms for some classes of combinatorial linear programs

ABSTRACT

We present greedy algorithms for some classes of combinatorial packing and cover problems within the general formal framework of Hoffman and Schwartz' lattice polyhedra. Our algorithms compute in a first phase Monge solutions for the associated dual cover and packing problems and then proceed to construct greedy solutions for the primal problems in a second phase. We show optimality of the algorithms under certain sub- and supermodular assumptions and monotone constraints. For supermodular lattice polyhedra with submodular constraints, our algorithms offer the farthest reaching generalization of Edmonds' polymatroid greedy algorithm currently known.

REFERENCES

• 1: {Duf62} R. F. Duffin, The extremal length of a network, Journal of Mathematical Analysis and Applications 5 (1962), 200--215.
• 2: {Edm70} J. Edmonds, Submodular functions, matroids and certain polyhedra, Proc. Int. Conf. on Combinatorics (Calgary), 1970, pp. 69--87.
• 3: {EJ85} P. H. Edelman and R. E. Jamison, The theory of convex geometries, Geometriae Dedicata 19 (1985), 247--270.
• 4: {FK00} U. Faigle and W. Kern, On the core of ordered submodular cost games, Math. Programming 87 (2000), 483--489.
• 5: {FP07} U. Faigle and B. Peis, Shapley's theorem and cooperative games with hierarchies, Working Paper (2007).
• 6: {Fra99} A. Frank, Increasing the rooted connectivity of a digraph by one, Math. Programming 84 (1999), 565--576.
• 7: {Fuj05} S. Fujishige, Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 58, Elsevier Science Publishers, North-Holland, 2nd ed., 2005.
• 8: {HS78} A. Hoffman and D. E. Schwartz, On lattice polyhedra, Proceedings of Fifth Hungarian Combinatorial Coll. (A. Hajnal and V. T. Sos, eds.), North-Holland, Amsterdam, 1978, pp. 593--598.
• 9: {Joh75} E. Johnson, On cut-set integer polyhedra, Cahiers du Centre d'Études de Recherche Opérationnelle 17 (1975), 235--251.
• 10: Maurice Queyranne , Frits Spieksma , Fabio Tardella, A General Class of Greedily Solvable Linear Programs, Mathematics of Operations Research, v.23 n.4, p.892-908, Nov. 1998 [doi>10.1287/moor.23.4.892]
• 11: {Rob56} J. T. Robacker, Min-max theorems on shortest chains and disjoint cuts of a network, Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California (1956).
• 12: {Sch03} A. Schrijver, Combinatorial Optimization, Springer, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms, Design, Theory