91. Relaxations for the elementary shortest path problem
Invited abstract in session FC-7: Optimization mosaics, stream Optimization in regression, classification and learning.
Friday, 11:25 - 12:40Room: M:I
Authors (first author is the speaker)
| 1. | Regina Schmidt
|
| University of Augsburg | |
| 2. | Mirjam Duer
|
| Augsburg University |
Abstract
Given a directed graph with negative arc costs and possibly negative cycles, the elementary shortst path problem consists in finding a shortest elementary path, i.e., a path from a source node to a target node that visits each node on the path exactly once. If negative arc costs are allowed, then the problem is NP-hard. In this talk, we discuss various formulations and relaxations for this problem.
Keywords
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers