Talk: abc-Optimization
Tuesday, 23.01.2018, 2018, 4:15pm
Location: Seminary room „SeMath“ in Mathegebäude, Pontdriesch 10, 52062 Aachen
Open to UnRAVeL-members, register at Dina Hermanns
16:15-17:15 Martin Skutella, TU Berlin: Stochastic scheduling on identical parallel machines
Minimizing the sum of weighted completion times on m identical parallel machines is one of the most important and classical scheduling problems. The talk is based on joint work with Sven Jäger.
17:15-17:45 Marc Schröder, RWTH Aachen: Negative Prices in Stackelberg Network Prices Games
A Stackelberg network pricing game is a two-stage game, in which, in the first stage, a leader sets prices/tolls for a subset of edges so as to maximize profit all other edges have a fixed cost, and, in the second stage, one or multiple followers choose a shortest path from their source to sink. Labbé et al. (1998) showed that finding optimal prices with lower bounds is NP-hard and gave an example in which profit is maximized by using negative prices. We explore this last phenomena and try to answer the following two questions. First, for which network topologies can the leader increase profit by using negative prices? Second, how much more profit can the leader realize by setting negative prices?
18:15-19:15 Marc Pfetsch, TU Damstadt: Symmetry Handling for Integer
The presence of symmetries in integer programs is well known to hurt the performance of branch-and-cut methods and several symmetry handling methods have been proposed. This talk will give an overview on these methods and investigate their computational impact. Most of these techniques perform pruning in the tree or fixing variables. As an alternative, a general polyhedral approach will be presented that is based on the convex hull of lexicographically maximal points within their orbit, so-called symretopes. While a complete description of these polytopes is only known for special symmetry groups, one can use their structure to construct efficiently solvable integer programming formulations. Computational results will show that this approach is competitive with the state-of-the-art methods based on pruning the tree.
18:15-19:15 Alexander Göke, Uni Bonn: Deleting Long Cycles in Directed Graphs
A well studied problem in approximation algorithms as well as parameterized complexity is the Feedback Vertex Set problem. Given a graph and an integer k, the task is to compute a set of k vertices such that deleting these vertices removes all cycles from the graph or to decide that no such set exists. The parameterized complexity status of the directed version was a long time open problem until it was shown to be fixed parameter tractable by Chen et al. [STOC 2008, J.ACM 2008]. We generalize this problem to the Bounded Circumference Feedback Vertex Set problem asking for a vertex set of size k such that its deletion removes all cycles of length greater than l. Using iterative compression and exploiting the structure of graphs with bounded circumference, we prove that the problem is fixed parameter tractable when parameterized in k and l.