Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms and Applications (1993) (Prentice Hall, New York) Google Scholar
• Ahuja R. K., Orlin J. B., Stein C., Tarjan R. E. Improved algorithms for bipartite network flow. SIAM J. Comput. (1994) 23:906–933Crossref, Google Scholar
• Arai T., Ueno S., Kajitani Y. Generalization of a theorem on the parametric maximum flow problem. Discrete Appl. Math. (1993) 41:69–74Crossref, Google Scholar
• Brumelle S., Granot D., Liu L. An extended economic selection problem. (1995a) . Manuscript, University of British Columbia Faculty of Commerce, Vancouver, BC, CanadaGoogle Scholar
• Brumelle S., Granot D., Liu L. Totally ordered optimal solutions and parametric maximum flows. (1995b) . Manuscript, University of British Columbia Faculty of Commerce, Vancouver, BC, CanadaGoogle Scholar
• Chen Y. L. Scheduling jobs to minimize total cost. Eur. J. Oper. Res. (1994) 74:111–119Crossref, Google Scholar
• Dinkelbach W. On nonlinear fractional programming. Management Sci. (1967) 13:492–498Link, Google Scholar
• Federgruen A., Groenevelt H. Preemptive scheduling of uniform machines by ordinary network flow techniques. Management Sci. (1986) 32:341–349Link, Google Scholar
• Fujishige S.Submodular Functions and Optimization. Ann. Discrete Math. (1991) 47(North-Holland, Amsterdam) Google Scholar
• Gallo G., Grigoriadis M. D., Tarjan R. E. A fast parametric maximum-flow algorithm and applications. SIAM J. Comput. (1989) 18:30–55Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability, A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company, New York) Google Scholar
• Goldberg A. V., Tarjan R. E. A new approach to the maximum flow problem. JACM (1988) 35(4):921–940Crossref, Google Scholar
• Gusfield D., Martel C. A fast algorithm for the generalized parametric minimum cut problem and applications. Algorithmica (1992) 7:499–519Crossref, Google Scholar
• Hall N. G., Vohra R. V. Towards equitable distribution via proportional equity constraints. Math. Prog. (1993) 58:287–294Crossref, Google Scholar
• Hochbaum D. S., Hong S.-P. About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Programming (1995) 69:269–309Crossref, Google Scholar
• Hoffman A., Rivlin J., Kuhn H. W. When is a team “mathematically” eliminated? Princeton Symposium on Math. Programming (1967) (Princeton University Press, Princeton, NJ) Google Scholar
• Horn W. A. Some simple scheduling algorithms. Naval Res. Logist. Quart. (1974) 21:177–185Crossref, Google Scholar
• Irving R. W., Leather P., Gusfield D. An efficient algorithm for the “optimal” stable marriage. J. ACM (1987) 34:532–543Crossref, Google Scholar
• Iwata S., Matsui T., McCormick S. T. A fast bipartite network flow algorithm for selective assembly. Oper. Res. Lett. (1998) 22:137–143Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Rinooy Kan A. H. G., Shmoys D. B., Graves S. C., Rinooy Kan A. H. G., Zipkin P. Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science (1993) 4(North-Holland, Amsterdam) . Chapter 9Google Scholar
• McCormick S. T., Liu L., Johnson D. S., McGeoch C. S. An experimental implementation of the dual cancel and tighten algorithm for minimum cost network flow. Network Flows and Matching (1993) 12(American Mathematical Society, Providence, RI) 247–266American Mathematical Society DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• McCormick S. T., Sahni J., Stewart T. A computational study of algorithms for finding ultimate contours of open-pit mines. (1997) . Working paperGoogle Scholar
• Megiddo N. Applying parallel computation algorithms in the design of serial algorithms. J. ACM (1983) 30:852–865Crossref, Google Scholar
• Radzik T. Newton's method for fractional combinatorial optimization. Proc. 33rd IEEE Annual Sympos. Foundations Comput. Sci. (1992) 659–669see also parametric flows, weighted means of cuts, and fractional combinatorial optimization. 1993. P. Pardalos, ed. Complexity in Numerical Optimization World Scientific, 351–386Crossref, Google Scholar
• Schwartz B. Possible winners in partially completed tournaments. SIAM Rev. (1966) 8:302–308Crossref, Google Scholar
• Serafini P. Scheduling jobs on several machines with the job splitting property. Oper. Res. (1996) 44:617–628Link, Google Scholar
• Topkis D. M. Minimizing a submodular function on a lattice. Oper. Res. (1978) 26:305–321Link, Google Scholar