Discipline: Computer Sciences and Information Management
Subcategory: Computer Science & Information Systems
Carlos Ontiveros - California State University Dominguez Hills
Co-Author(s): Bin Tang, California State University Dominguez Hills, CA
Network flows studies how to move entities or objects, such as electrical currents, goods, vehicles, and network packets, from one point in a network to another point efficiently, while utilizing the underlying network resources cost-effectively. Coupling deep theoretical rigor and remarkable range of applicability, network flows spans over several broad disciplines including operations research, computer science, and engineering. In particular, the classic maximum flow problem finds the maximum amount of flow that can be sent from source node to sink node in a flow network, considering that edges in the flow network have capacities that restrain amount of flows on each edge. It has wide real world applications such as baseball elimination, airline scheduling, job scheduling, and network routing. The push-relabel algorithm is one of the most efficient algorithms for the maximum flow problem. Push operation and relabel operation are two basic operations used in the algorithm. In particular, during the execution of the algorithm, it maintains a ‘preflow’ and gradually converts it into a maximum flow by moving flow locally between neighboring vertices using push operations under the guidance of an admissible network maintained by relabel operations. Cherkassky and Goldberg (‘On Implementing Push-Relabel Method for the Maximum Flow Problem,’ Algorithmica 19 (1997), 390 — 410) proposed an efficient implementation of the push-relabel algorithm for the maximum flow (available at http://www.avglab.com/andrew/soft.html). However, classic maximum flow fails to consider that different flow could have different weights or values. For example, in sensor networks, data collected by different sensors could have different values for the scientists to analyze the physical world. In this abstract, we study the maximum weighted flow problem, which is to maximize the total weight of flow in the network considering different flows have different weights. Maximum weighted flow is a generalization of the classic maximum flow problem, wherein each unit of flow has the same weight. We design an efficient optimal algorithm for maximum weighted flow problem. We implement our algorithm by modifying the implementation by Cherkassky and Goldberg and including the concept of the flow weights into the design and implementation. We generate different graph families using three graph generators available from DIMACS. Via extensive simulation, we show that it outperforms the push-relabel maximum flow algorithm in terms of the total preserved priorities.
Funder Acknowledgement(s): This work was supported in part by NSF Grants CNS-1116849 and #HRD-1302873, and the Chancellor’s Office of the California State University. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or the Chancellor’s Office of the CSU.
Faculty Advisor: Bin Tang,