Free Access
RAIRO-Oper. Res.
Volume 21, Number 2, 1987
Page(s) 105 - 136
Published online 06 February 2017
  • Y. P. ANEJA, An Integer Linear Programming Approach to the Steiner Problem in Graphs, Networks, Vol. 10, 1980, pp. 167-178. [MR: 569008] [Zbl: 0445.90087] [Google Scholar]
  • E. BALAS and M. W. PADBERG, On the Set Covering Problem, II. An Algorithm for Set Partitioning, Operations Research, Vol. 23, 1975, pp. 74-90. [MR: 411622] [Zbl: 0324.90045] [Google Scholar]
  • E. BALAS and M. W. PADBERG, Set Partitioning: a Survey in Combinatorial Optimizaion, N. CHRISTOFIDES, A. MINGOZZI, P. TOTH and C. SANDI Eds., J. Wiley and Sons, 1979, pp. 151-210. [Zbl: 0413.90047] [Google Scholar]
  • E. BALAS and Ho, Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimization: A Computational Study, Mathematical Programming Study, Vol. 12, 1980, pp. 37-60. [MR: 571854] [Zbl: 0435.90074] [Google Scholar]
  • C. BERGE, Graphes et Hypergraphes, Dunod, Paris, 1970. [MR: 357173] [Zbl: 0213.25702] [Google Scholar]
  • A. BILLIONNET and M. MINOUX, Maximizing a Supermodular Pseudoboolean Function: Polynomial Algorithm for Supermodular Cubic Functions, Discrete Applied Mathematics, Vol. 12, 1985, pp. 1-11. [MR: 798006] [Zbl: 0583.90067] [Google Scholar]
  • A. BILLIONNET and M. MINOUX, Bounds and Efficient Algorithms for Submodular Pseudoboolean Function Minimization, 1984, To appear under the title: Duality Results and related Algorithms for Submodular function minimization. [Google Scholar]
  • G. B. DANTZIG, Linear Programming and Extensions, Princeton University Press, Princeton, 1963. [MR: 201189] [Zbl: 0997.90504] [Google Scholar]
  • G. B. DANTZIG and P. WOLFE, The Decomposition Algorithm for Linear Programming, Econometrica, Vol. 29, No. 4, 1961, pp. 767-778. [MR: 138506] [Zbl: 0104.14305] [Google Scholar]
  • J. DELORME, Contribution à la résolution du problème de recouvrement : méthodes de troncatures, Thèse de Docteur Ingénieur, Université Paris-VI, 1974. [Google Scholar]
  • J. DESROSIERS, F. SOUMIS and M. DESROCHERS, Routing with Time Windows by Column Generation, Networks, Vol 14, 1984, pp. 545-565. [Zbl: 0571.90088] [Google Scholar]
  • E. A. DINIC, Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation, Soviet Math. Dokl., Vol. 11, 1970, pp.1277-1280. [Zbl: 0219.90046] [Google Scholar]
  • J. EDMONDS, Maximum Matching and a Polyhedron with 0-1 Vertices, Journal Res. Nat. Bureau Standards, Vol. 69-B, Nos. 1-2, 1965, pp. 125-130. [MR: 183532] [Zbl: 0141.21802] [Google Scholar]
  • J. EDMONDS, Optimum Branchings, J. Res. Nat. Bur. Stand. B. Vol. 71, 1967, pp. 233-240. [MR: 227047] [Zbl: 0155.51204] [Google Scholar]
  • J. EDMONDS, Submodular Functions, Matroïds, and Certain Polyhedra in Combinatorial tructures and their Applications, R. GUY Ed., Gordon and Breach, New York, 1970, pp. 69-87. [MR: 270945] [Zbl: 0268.05019] [Google Scholar]
  • J. EDMONDS, Matroïds and the Greedy Algorithm, Mathematical Programming, Vol. 1, 1971, pp. 127-136. [MR: 297357] [Zbl: 0253.90027] [Google Scholar]
  • M. L. FISCHER, G. L. NEMHAUSER and L. A. WOLSEY, An Analysis of Approximations for Maximizing Submodular Set Functions I, Math. Programming Vol. 14, 1978, pp. 265-294. [MR: 503866] [Zbl: 0374.90045] [Google Scholar]
  • H. N. GABOW, Implementations of Algorithms for Maximum Matchings on Non-Bipartite Graphs, Ph. D. Dessertation, Computer Sc. Departement, Stanford University, California, 1973. [Google Scholar]
  • M. R. GAREY and D. S. JOHNSON, Computers and Intractability. An Introduction to the Theory of NP-Complteteness, W. H. Freeman and Co., San Francisco, 1979. [MR: 519066] [Zbl: 0411.68039] [Google Scholar]
  • R. S. GARFINKEL and G. L. NEMHAUSER, The Set Partitioning Problem: Set Covering with Equality Constraints, Operations Research, Vol. 17, 1969, pp. 848-856. [Zbl: 0184.23101] [Google Scholar]
  • P. C. GILMORE and R. E. GOMORY, A Linear Programming Approach to the Cutting-Stock Problem. Part II, Operations Research, Vol. 11, 1963, pp. 863-888. [Zbl: 0124.36307] [Google Scholar]
  • R. E. GOMORY and T. C. Hu, An Application of Generalized Linear Programming to Network Flows, Journal S.I.A.M., Vol. 10, No. 2, 1962, pp. 260-283. [MR: 204155] [Zbl: 0105.12805] [Google Scholar]
  • M. GONDRAN and M. MINOUX, Graphes et Algorithmes, Eyrolles, Paris, 1979, English translation, J. Wiley and Sons, 1983. [MR: 615739] [Zbl: 0497.05023] [Google Scholar]
  • M. GROTSCHEL, L. LOVÂSZ and SCHRIJVER, The Ellipsoïd Method and its Consequences in Combinatorial Optimization, Combinatorica, Vol. 1, No. 2, 1981, pp. 169-197. [MR: 625550] [Zbl: 0492.90056] [Google Scholar]
  • S. L. HAKIMI, Optimum Location of Switching Centers and the Absolute Centers and Medians of a Graph, Operations Research, Vol. 12, 1964, pp. 450-459. [Zbl: 0123.00305] [Google Scholar]
  • J. HALPERN and I. PRIESS, Shortest Path with Time Constraints on Movement and Parking, Networks, Vol. 4, 1974, pp. 241-253. [MR: 347378] [Zbl: 0284.90077] [Google Scholar]
  • P. HANSEN, D. PEETERS and J. F. THISSE, Facility Location Analysis, Rutcor Research Report 4-85, Rutgers University (NJ), 1985, Encyclopedia of Economics (to appear). [Zbl: 0618.90028] [Google Scholar]
  • P. HANSEN, Private communication, 1986. [Google Scholar]
  • I. HOLYER, The NP-Completeness of Edge-Coloring, S.I.A.M. J. Comput., Vol. 10, No. 4, 1981, pp. 718-720. [MR: 635430] [Zbl: 0473.68034] [Google Scholar]
  • T. INUKAI, Comments on Analysis of a Switch Matrix for an SS/TDMA System, Proceedings of the I.E.E.E., Vol. 66, No. 12, 1978, pp. 1669-1670. [Google Scholar]
  • Y. ITO, Y. URANO, T. MURATANI and M. YAMAGUCHI, Analysis of a Switch Matrix for an SS/TDMA System, Proceedings of the I.E.E.E., Vol. 65, No. 3, 1977, pp. 411-419. [MR: 434597] [Google Scholar]
  • A. V. KARZANOV, Determining the Maximal Flow in a Network by the Method of Preflows, Soviet Math. Dokl., Vol. 15, 1974, pp. 434-437. [Zbl: 0303.90014] [Google Scholar]
  • L. G. KHACHIAN, A Polvnomial Algorithm in Linear Programming, Soviet Math Dokl., Vol. 20, No. 1, 1979, pp. 191-194. [Zbl: 0414.90086] [Google Scholar]
  • L. S. LASDON, Optimization Theory for Large Systems, Macmillan series for Operations Research, 1970. [MR: 337317] [Zbl: 0224.90038] [Google Scholar]
  • S. LAVOIE, M. MINOUX and E. ODIER, A new Approach of Crew Pairing Problems by Column Generation and Application to Air Transports, 1985(to Appear). [Zbl: 0636.90041] [Google Scholar]
  • E. LAWLER, Combinatorial Optimization. Networks and Matroïds, Holt, Rinehart and Winston, 1976. [MR: 439106] [Zbl: 0413.90040] [Google Scholar]
  • C. E. H. LEMKE, M. SALKIN and K. SPIELBERG, Set Covering by Single Branch Enumeration with Linear Programming Subproblems, Operations Research, Vol. 19, 1971, pp . 998-1022. [MR: 418914] [Zbl: 0232.90033] [Google Scholar]
  • N. MACULAN, The Steiner Problem in Graphs, in Surveys in Combinatorial Optimization, S. MARTELLO, G. LAPORTE, M. MINOUX and C. RIBEIRO Eds., North Holland, 1987. [MR: 878773] [Zbl: 0622.90029] [Google Scholar]
  • V. M. MALHOTRA, M. P. KUMAR and S. N. MAHESHWARI, An O (IVI3 ) Algorithm for finding Maximum Flows in Networks, Information Processing Letters, Vol.7, No. 6, 1978, pp. 277-278. [MR: 509428] [Zbl: 0391.90041] [Google Scholar]
  • F. E. MARANZANA, On the Location of Supply Points to Minimize Transport Costs, Operational Research Quarterly, Vol. 15, 1964, pp. 261-270. [Google Scholar]
  • R. E. MARSTEN, An Algorithm for Large Set Partitioning Problems, Management Science, Vol. 20, 1974, pp.779-787. [MR: 342177] [Zbl: 0304.90077] [Google Scholar]
  • M. MINOUX, Plus court chemin avec contraintes, algorithmes et applications, Annales des Télécommunications, Vol. 30, Nos. 11-12, 1975, pp. 383-394. [Zbl: 0347.90065] [Google Scholar]
  • M. MINOUX, Programmation Mathématique: Théorie et Algorithmes, Dunod Paris, 1983, English Translation, J. Weley and Sons, 1986. [MR: 2571910] [Zbl: 0546.90056] [Google Scholar]
  • M. MINOUX, Optimal Traffic Assignment in a SS/TDMA Frame: A New Approach by Set Covering and Column Generation, O.R.S.A./T.I.M.S. meeting, Dallas, Texas, 1984a, R.A.I.R.O., Vol. 20, No. 4, 1986, pp. 1-13. [EuDML: 104906] [Zbl: 0608.90076] [Google Scholar]
  • M. MINOUX, Column Generation Techniques in Combinatorial Optimization: A New Application to Crew-Pairing Problems, XXIVth AGIFORS Symposium, 1984 b, Strasbourg, France, september 1984. [Google Scholar]
  • M. MINOUX, New Lower Bounds to the Graph Partitioning Problem through Generalized Linear Programming and Network Flows, 1986a (to be published). [Zbl: 0657.90095] [Google Scholar]
  • M. MINOUX, Solving Combinatorial Problems with Combined Min-Max-Min-Sum objective, 1986a (under preparation). [Zbl: 0682.90076] [Google Scholar]
  • C. St. J. A. NASH-WILLIAMS, Decomposition of Finite Graphs into Forests, Journal London Math. Soc, Vol. 39, 1964, p. 12. [MR: 161333] [Zbl: 0119.38805] [Google Scholar]
  • C. St. J. A. NASH-WILLIAMS, An Application of Matroïds to Graph Theory in Theorie des Graphes, Proceedings Internat. Symposium, Rome, Italy, 1966, Dunod, Paris, 1967. [Zbl: 0188.55903] [Google Scholar]
  • R. C. PRIM, Shortest Connection Networks and Some Generalizations, Bell Syst. Techn. J., Vol. 36, 1957, p. 1389. [Google Scholar]
  • F. RENDL, On the Complexity of Decomposing Matrices Arising in Satellite Communications, Bericht 84-47, Technische Universität, Graz, Austria, 1984. [Zbl: 0569.90064] [Google Scholar]
  • J. M. W. RHYS, A Selection Problem of Shared Fixed Costs and Network Flows, Management Science, Vol. 17, No. 3, 1970, pp. 200-207. [MR: 309537] [Zbl: 0203.52505] [Google Scholar]
  • C. RIBEIRO, M. MINOUX and C. PENNA, A Hybrid Branch and Bound/Column Generation Approach to Very Large Scale Set Covering Problems with Special Structure, O.R.S.A./T.I.M.S. meeting, Miami, Florida, November 1986 (to Appear). [MR: 858854] [Google Scholar]
  • N. Z. SHOR, Cut-off Methods with Space Extension in Convex Programming Problems, Kibernetika, Vol. 13, No. 1, 1977, pp. 94-95, English Translation in Cybernetics, Vol. 13, No. 1, 1977, pp. 94-96. [Zbl: 0365.90104] [Google Scholar]
  • R. E. TARJAN, A simple Version of Karzanov's Blocking Flow Algorithm, Operations Research Letters, Vol. 2, No.6, 1984, pp. 265-268. [MR: 739677] [Zbl: 0542.05057] [Google Scholar]
  • L. VISMARA, Piano di accesso dei messaggi insistemi SS/TDMA: un metodo di enumerazione implicita per minimizzare il tempo di transmissione, Tesi di laurea, politechnico di Milano, Departamento di Elettronica (Paolo Camerini i Francesco Maffioli Relatori), 1982. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.