direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

An instance-specific hardness measure for the Airplane Refueling Problem: a parameterized perspective

Junjie Luo (TU Berlin)


The airplane refueling problem is a nonlinear combinatorial optimization problem and it can be transformed into a single-machine scheduling problem which maximizes the weighted sum of inverse completion times. Its complexity status is still open and the hardness of solving different instances of the same size can vary greatly. To provide information for choosing a proper algorithm to solve a specific instance of this problem, we give an instance-specific hardness measure for this problem from a parameterized perspective. We first characterize the global precedence relations of pairwise jobs by a permutation and show the problem is fixed-parameter solvable with respect to two structural parameters of the permutation graph: vertex integrity and treewidth. For the first parameter vertex integrity, we device an algorithm with running time \(O(2^{k+s}(k+s)n)\), where \(n\) is the input size and \(k+s\) is the parameter vertex integrity. For treewidth, which is always smaller than vertex integrity for a permutation graph, we device an algorithm with running time \(O(2^wwn)\), where \(w\) is the treewidth. As the treewidth for a permutation graph can be computed in \(O(nw^2)\) time, we can predict the running time of this algorithm on any specific instance, in polynomial time, before solving this instance. With this running time, we can make the right choice between the parameterized algorithm, approximation algorithms and heuristic algorithms to solve the instance at hand.


Junjie Luo
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras