3 citations · 11 across the 8 of their papers we have counts for
8 papers
A linear time algorithm for linearizing quadratic and higher-order shortest path problems
Eranda Çela, Bettina Klinz, Stefan Lendl +2
An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same…
The bipartite travelling salesman problem: A pyramidally solvable case
Vladimir G. Deineko, Bettina Klinz, Gerhard J. Woeginger
In the bipartite travelling salesman problem (BTSP), we are given cities along with an distance matrix and a partition of the cities into red and blue ci…
2-Period Balanced Travelling Salesman Problem: a polynomially solvable case and heuristics
Vladimir Deineko, Bettina Klinz, Mengke Wang
We consider the NP-hard 2-period balanced travelling salesman problem. In this problem the salesman needs to visit a set of customers in two time periods. A given subset of the cus…
2VRP: a benchmark problem for small but rich VRPs
Vladimir Deineko, Bettina Klinz
We consider a 2-vehicle routing problem (2VRP) which can be viewed as a building block for the variety of vehicle routing problems (VRP). As a simplified version of the 2VRP, we co…
Geometric versions of the 3-dimensional assignment problem under general norms
Ante Ćustić, Bettina Klinz, Gerhard J. Woeginger
We discuss the computational complexity of special cases of the 3-dimensional (axial) assignment problem where the elements are points in a Cartesian space and where the cost coeff…
Planar 3-dimensional assignment problems with Monge-like cost arrays
Ante Ćustić, Bettina Klinz, Gerhard J. Woeginger
Given an cost array we consider the problem -P3AP which consists in finding pairwise disjoint permutations of s…
The constant objective value property for combinatorial optimization problems
Ante Ćustić, Bettina Klinz
Given a combinatorial optimization problem, we aim at characterizing the set of all instances for which every feasible solution has the same objective value. Our central result dea…
Uniqueness in quadratic and hyperbolic 0-1 programming problems
Vladimir G. Deineko, Bettina Klinz, Gerhard J. Woeginger
We analyze the question of deciding whether a quadratic or a hyperbolic 0-1 programming instance has a unique optimal solution. Both uniqueness questions are known to be NP-hard, b…