On algorithmic approaches for the S-labeling problem

Description

In this talk, we present algorithmic approaches for the recently introduced S-labeling problem, in which the nodes get labeled using labels from 1 to|V|and for each edge the contribution to the objective function, called S-labeling number of the graph, is the minimum label of its end-nodes. The goal is to find a labeling with minimum value.The problem is NP-hard for planar subcubic graphs, although for many other graph classes the complexity status is still unknown.We present different algorithmic approaches for tackling this problem:We develop an exact solution framework based on Mixed-Integer Programming (MIP) which is enhanced with valid inequalities, starting and primal heuristics and specialized branching rules. Moreover, we also present a dual-ascent-like heuristic, a Lagrangian heuristic and a constraint programming approach. Finally, we give, to the best of our knowledge, the first polynomial-time algorithm for the problem on complete n-ary trees as well as a closed formula for the S-labeling number for such trees

Period	05 Sept 2019
Event title	Operations Research 2019
Event type	Conference
Location	GermanyShow on map