2206. Sparse Solutions for Network Optimization Problems
Invited abstract in session WB-4: Network Optimization, stream Discrete and Combinatorial Optimization.
Wednesday, 10:45-12:15Room: H6
Authors (first author is the speaker)
| 1. | Arie Koster
|
| Lehrstuhl II für Mathematik, RWTH Aachen University | |
| 2. | Pauline Lückemann
|
| RWTH Aachen University |
Abstract
A solution is called sparse if there the encoding vector has only few nonzero entries. In many practical applications, sparse solutions have (managerial, operational) benefits that need to be considered in addition to the original objective function. In this presentation, we discuss three fundamental network optimization problems and the impact of sparsity on them: Sparse Shortest Path remains polynomial time solvable, Sparse Maximum Flow and Sparse Minimum Cost Flow become NP-complete in general graphs. For series parallel graphs, we provide polynomial and pseudo-polynomial algorithms for the latter two cases.
Keywords
- Combinatorial Optimization
- Graphs and Networks
- Routing
Status: accepted
Back to the list of papers