Lower bounds to the graph partitioning problem through generalized linear programming and network flows

M. Minoux; E. Pinson

RAIRO - Operations Research - Recherche Opérationnelle (1987)

  • Volume: 21, Issue: 4, page 349-364
  • ISSN: 0399-0559

How to cite

top

Minoux, M., and Pinson, E.. "Lower bounds to the graph partitioning problem through generalized linear programming and network flows." RAIRO - Operations Research - Recherche Opérationnelle 21.4 (1987): 349-364. <http://eudml.org/doc/104928>.

@article{Minoux1987,
author = {Minoux, M., Pinson, E.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {exact solution; graph partitioning; branch-and-bound; sharp bounds; large-scale set partitioning; large-scale Boolean linear programming; continuous relaxation; column generation subproblem; quadratic pseudo- Boolean minimization; max-flow; polynomial solvability},
language = {eng},
number = {4},
pages = {349-364},
publisher = {EDP-Sciences},
title = {Lower bounds to the graph partitioning problem through generalized linear programming and network flows},
url = {http://eudml.org/doc/104928},
volume = {21},
year = {1987},
}

TY - JOUR
AU - Minoux, M.
AU - Pinson, E.
TI - Lower bounds to the graph partitioning problem through generalized linear programming and network flows
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1987
PB - EDP-Sciences
VL - 21
IS - 4
SP - 349
EP - 364
LA - eng
KW - exact solution; graph partitioning; branch-and-bound; sharp bounds; large-scale set partitioning; large-scale Boolean linear programming; continuous relaxation; column generation subproblem; quadratic pseudo- Boolean minimization; max-flow; polynomial solvability
UR - http://eudml.org/doc/104928
ER -

References

top
  1. BARNES E. R., An Algorithm for Partitioning the Nodes of a Graph, SIAM J. Alg. Discr. Meth. Vol. 4, 1982, pp. 541-550. Zbl0505.05050MR679649
  2. BENDERS J. F., Partitioning Procedures for solving mixed variables programming problems, Numerische Mathematik, Vol. 4, 1962, pp. 238-252. Zbl0109.38302MR147303
  3. CHRISTOFIDES N. and BROOKER P., The Optimal Partitioning of Graphs, SIAM J. Appl. Math. Vol. 30, No. 1, 1976, pp. 55-70. Zbl0321.05123MR405911
  4. DANTZIG G. B. and WOLFE P., The Decomposition Algorithm for Linear Programming, Econometrica, Vol. 29, No. 4, 1961, pp. 767, 778. Zbl0104.14305MR138506
  5. DINIC E. A., Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation, Soviet Math. Dokl., Vol. 11, 1970, pp. 1277-1280. Zbl0219.90046
  6. HAMMER P. L., HANSEN P. and SIMEONE B., Roof Duality, Complementation and Persistency in Quadratic 0-1 Optimization, Mathematical Programming, Vol. 28, 1984, pp. 121-155. Zbl0574.90066MR733206
  7. HANSEN P. and ROUCAIROL C., Problème de la bipartition minimale d'un graphe, RAIRO (à paraître). Zbl0628.90049
  8. HYAFIL L. and RIVEST R. L., Graph Partitioning and Constructing Optimal Decision Trees are Polynomial Complete Problems, Report n° 33, IRIA-Laboria, Rocquencourt, France, 1973. 
  9. KARZANOV A. V., Determining the Maximal Flow in a Network by the Method of Preflows, Soviet Math. Dokl. Vol. 15, 1974, pp. 434-437. Zbl0303.90014
  10. LU S. M. and WILLIAMS A. C., Roof Duality for Nonlinear 0-1 Optimization, Rutcor Research Report, RRR 2-85, 1985. 
  11. MINOUX M., Programmation Mathématique : théorie et algorithmes, Dunod, Paris, 1983 (English translation J. Wiley & Sons, 1986). Zbl0546.90056MR2571910
  12. MINOUX M.Optimal Traffic Assignaient in a SS/TDMS Frame: a New Approach by Set Covering and Column Generation, ORSA/TIMS meeting, Dallas, Texas, 1984, Appeared in RAIRO, Vol. 20, No. 4, 1986, pp. 1-13. Zbl0608.90076
  13. MINOUX M., A Class of Combinatorial Problems with Polynomially Solvable Large Scale set Covering/Partitioning Relaxations, Journées du 20e anniversaire du Groupe Combinatoire de l'AFCET, Paris-3, 5 décembre 1986, appeared in RAIRO, Vol. 21, No. 2, 1987, pp. 105-136. Zbl0644.90061MR897292
  14. RHYS J. M. W., A Selection Problem of Shared Fixed Costs and Network Flows, Management Science, Vol. 17, No. 3 (1970), pp. 200-207. Zbl0203.52505MR309537
  15. RIBEIRO C., MINOUX M. et PENNA C., A Combined Branch and Bound/Column generation Approach to very large Scale Set Covering Problems with Special Structure, ORSA/-TIMS meeting, Miami, Florida, November 1986, (to appear). MR858854
  16. ROSENBERG I. G., Reduction of Bivalent Maximization to the Quadratic Case, Cahiers du Centre d'Études de Recherche Opérationnelle, Vol. 17, 1975, pp.71-79. Zbl0302.90041MR378807
  17. TARJAN R. E., A Simple Version of Karzanov's Blocking Flow Algorithm, Operations Research Letters, Vol. 2, No. 6 (1984), pp. 265-268. Zbl0542.05057MR739677
  18. WILLAMS A. C., Quadratic 0-1 Programming Using the roof Dual with Computational Results, RUTCOR Research Report RRR8-85, 1985. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.