We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive semidefinite matrix of rank at most $k$. We show that this problem is $\NP$-hard for any fixed integer $k\ge 2$. Equivalently, for $k\ge 2$, it is $\NP$-hard to test membership in the … Read more
It is well known that the standard (linear) knapsack problem can be solved exactly by dynamic programming in O(nc) time, where n is the number of items and c is the capacity of the knapsack. The quadratic knapsack problem, on the other hand, is NP-hard in the strong sense, which makes it unlikely that it … Read more
The Steiner Traveling Salesman Problem (STSP) is a variant of the Traveling Salesman Problem (TSP) that is particularly suitable when dealing with sparse networks, such as road networks. The standard integer programming formulation of the STSP has an exponential number of constraints, just like the standard formulation of the TSP. On the other hand, there … Read more
Pisinger et al. introduced the concept of `aggressive reduction’ for large-scale combinatorial optimisation problems. The idea is to spend much time and effort in reducing the size of the instance, in the hope that the reduced instance will then be small enough to be solved by an exact algorithm. We present an aggressive reduction scheme … Read more
The single row facility layout is the NP-Hard problem of arranging facilities with given lengths on a line, so as to minimize the weighted sum of the distances between all pairs of facilities. Owing to the computational complexity of the problem, researchers have developed several heuristics to obtain good quality solutions. In this paper, we … Read more
We introduce an algorithm design technique for a class of combinatorial optimization problems with concave costs. This technique yields a strongly polynomial primal-dual algorithm for a concave cost problem whenever such an algorithm exists for the fixed-charge counterpart of the problem. For many practical concave cost problems, the fixed-charge counterpart is a well-studied combinatorial optimization … Read more
Within the context of the standard model of rationality within economic modelling we show the existence of a utility function that rationalises a demand correspondence, hence completely characterizes the associated preference structure, by taking a dense demand sample. This resolves the problem of revealed preferences under some very mild assumptions on the demand correspondence which … Read more
We consider the facility location problem with submodular penalty (FLPSP) and the facility location problem with linear penalty (FLPLP), two extensions of the classical facility location problem (FLP). First, we introduce a general algorithmic framework for a class of covering problems with submodular penalty, extending the recent result of Geunes et al. [12] with linear … Read more
Facility location-network design problems seek to simultaneously determine the locations of fa- cilities and the design of the network connecting the facilities so as to best serve a set of clients accessing the facilities via the network. Here we study a dynamic (multi-period) version of the problem, subject to a budget constraint limiting the investment … Read more
We study the problem of minimizing a nonnegative separable concave function over a compact feasible set. We approximate this problem to within a factor of 1+epsilon by a piecewise-linear minimization problem over the same feasible set. Our main result is that when the feasible set is a polyhedron, the number of resulting pieces is polynomial … Read more