2016/10/13 by Dorit S. Hochbaum, Hochbaum, Dorit S.
Computer Science · Decision Sciences · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.0 #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #Operations research #Resource-Constrained Project Scheduling #mathematical programming
paper · pdf · doi:10.48550/arxiv.1610.04012
openalex publication_date 2016/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We explore here surprising links between the time-cost-tradeoff problem and the minimum cost flow problem that lead to fast, strongly polynomial, algorithms for both problems. One of the main results is a new algorithm for the unit capacity min cost flow that matches the complexity of the fastest strongly polynomial algorithm known for the assignment problem. The time cost tradeoff (TCT) problem in project management is to expedite the durations of activities, subject to precedence constraints, in order to achieve a target project completion time at minimum expediting costs, or, to maximize the net benefit from a reward associated with project completion time reduction. Each activity is associated with integer normal duration, minimum duration, and expediting cost per unit reduction in duration. We devise here the \em all-min-cuts procedure, which for a given maximum flow, is capable of generating all minimum cuts (equivalent to minimum cost expediting) of equal value very efficiently. Equivalently, the procedure identifies all solutions that reside on the TCT curve between consecutive breakpoints in average O(m+n log n) time, where m and n are the numbers of arcs and nodes in the network. The all-min-cuts procedure implies faster algorithms for certain TCT problems and for certain min cost flow problem with a significantly different approach from the ones known.