In 1996, Laurent and Poljak introduced an extremely general class of cutting planes for the max-cut problem, called gap inequalities. We prove several results about them, including the following: (i) there must exist non-dominated gap inequalities with gap larger than 1, unless NP = co-NP; (ii) there must exist non-dominated gap inequalities with exponentially large … Read more
We show that the most cost-efficient subset problem for linear programming games is NP-hard, and in fact inapproximable within a constant factor in polynomial time, unless P = NP. This in turn implies that computing the prices output by an egalitarian mechanism and computing a cost allocation in the equal split-off set for linear programming … Read more
In this paper we propose an adaptation of the GRASP metaheuristic to solve multi-objective combinatorial optimization problems. In particular we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with path-relinking for single-objective optimization. In this paper, we propose different … Read more
Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality \begin{equation} \label{le} per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n \end{equation} We prove in this paper the following generalization (or just clever reformulation) of (\ref{le}):\\ For all … Read more
Given a graph $G=([n],E)$ and $w\in\R^E$, consider the integer program ${\max}_{x\in \{\pm 1\}^n} \sum_{ij \in E} w_{ij}x_ix_j$ and its canonical semidefinite programming relaxation ${\max} \sum_{ij \in E} w_{ij}v_i^Tv_j$, where the maximum is taken over all unit vectors $v_i\in\R^n$. The integrality gap of this relaxation is known as the Grothendieck constant $\ka(G)$ of $G$. We present … Read more
We propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, … Read more
In many telecommunication network architectures a given set of client nodes must be served by different kinds of facility, which provide di fferent services and have diff erent capabilities. Such facilities must be located and dimensioned in the design phase. We tackle a particular location problem in which two sets of facilities, mid level and high level, … Read more
We consider an uncertain variant of the knapsack problem that arises when the exact weight of each item is not exactly known in advance but belongs to a given interval, and the number of items whose weight differs from the nominal value is bounded by a constant. We analyze the worsening of the optimal solution … Read more
The use of metaheuristics in Multi-objective Combinatorial Optimization, particularly Ant Colony Optimization (ACO), has grown recently. This paper proposes an approach where multi-species ants compete for food resources. Each species has its own search strategy and do not access pheromone information of other species. As in nature, successful ant populations are allowed to grow, whereas … Read more
In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We … Read more