Fast, Exact, and Approximate Algorithms in Network and Combinatorial Optimization
Abstract
Everywhere we look in our lives, networks are present: electrical and power networks, communication networks,transportation networks, distribution networks, and social networks. To deal effectively with networks, researchers have developed thousands of algorithms that solve the fundamental problems underlying these networks. The PI of this proposal has been actively involved in developing efficient algorithms for network problems for more than 30 years, and has co--~authored the standard reference in the area of ~network flows.~Two fundamental concepts within networks (and also within graph theory) are the concepts of path and cycle. The PI proposes to carry out research that will improve algorithms concerned with these two problems.An extremely well--~known problem within the studies of networks and graphs is the shortest path problem. In thisproblem, the goal is to determine the shortest distance from a given source node S to a given destination node T in a network (directed graph) G. A closely related problem is that of finding the shortest cycle in a network. Together with a collaborator, the PI has recently developed the fastest algorithm (in terms of worst case complexity) for the shortest cycle problem. Part of the proposed research is to explore ramifications of the new algorithm and explore how efficient it is in practice.A related problem with cycles is to find a cycle whose cost is negative. This problem is a fundamental subproblem in solving more complex problems such as minimum cost flows, and problems in logic. A special case of the negative cost cycle problem is to find a negative cost cycle with the fewest number of edges (arcs). This special case has applications in logic as well as in market equilibrium analysis. Together with a collaborator, the PI has recently developed a very fast randomized algorithm for this special case. Part of the proposed research is to explore ramifications of the new algorithm and explore how efficient it is in practice.The PI also plans to explore other fundamental problems in graph and network theory, including a fundamental problem in parallelism. How much can the shortest path algorithm be sped up if one can use a large number of parallel processors?In addition, the PI plans to investigate graph problems as well as stochastic optimization problems that are NP--~hard (or possibly even #P--~hard). Of special interest are algorithms that guarantee solutions that are within ~ of optimal and whose running time is polynomial in the size of the problem and in 1/~. Such an algorithm is referred to as a Fully Polynomial Time Approximation Scheme (FPTAS). The PI has carried out research with others on classifying stochastic optimization problems that have an FPTAS. The PI has also developed faster FPTASs for several variants of the Knapsack Problem. The PI proposes to continue this line of research and to identify new combinatorial optimization problems (especially stochastic optimization problems) for which an FPTAS can be developed. And in cases in which there is an FPTAS, the PI proposes to develop as fast an FPTAS as possible.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 03, 2017
- Source ID
- N000141712194
Entities
People
- James B. Orlin
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy