Premium
Algorithms for source‐to‐all maximum cost‐to‐time ratio problem in acyclic networks
Author(s) -
Makri Alexandra,
Klabjan Diego
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10070
Subject(s) - correctness , computer science , node (physics) , mathematical proof , time complexity , path (computing) , mathematical optimization , algorithm , mathematics , computer network , geometry , structural engineering , engineering
Abstract The source‐to‐all maximum cost‐to‐time ratio problem is the problem of finding the maximum cost‐to‐time ratio path from a source node to every other node. The motivation comes from an application in large‐scale linear programming. We present three algorithms for solving the problem. We give proofs of correctness and we analyze the running times. One of the algorithms is polynomial and the remaining two are pseudopolynomial. We present extensive computational results on several networks. © 2003 Wiley Periodicals, Inc.