A traffic matrix $D^1$ dominates a traffic matrix $D^2$ if $D^2$ can be routed on every (capacitated) network where $D^1$ can be routed. We prove that $D^1$ dominates $D^2$ if and only if $D^1$, considered as a capacity vector, supports $D^2$. We show several generalizations of this result. CitationCentro Vito Volterra, Universita’ di Roma Tor … Read more
In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson. We first develop a closed-form formula to compute the probability of … Read more
In this article, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) to generate a good approximation of the efficient or Pareto optimal set of a multi-objective combinatorial optimization problem. The algorithm is applied for the 0/1 knapsack problem with r objective functions. This problem is formulated as r classic 0/1 knapsack problems. n items, … Read more
Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize … Read more
We adapt a method due to Nesterov so as to obtain an algorithm for solving block-angular fractional packing or covering problems to relative tolerance epsilon, while using a number of iterations that grows polynomially in the size of the problem and whose dependency on epsilon is proportional to 1/epsilon. CitationCORC report TR-2004-09, Computational Optimization Research … Read more
We show that for any fixed rank, the closure of a set covering problem (and related problems) can be approximated in polynomial time — we can epsilon-approximate any linear program over the closure in polynomial time. CitationCORC report TR-2003-01, Computational Optimization Research Center, Columbia UniversityArticleDownload View PDF
Polynomially testable characterization of cost matrices associated with a complete digraph on $n$ nodes such that all the Hamiltonian cycles (tours) have the same cost is well known. Tarasov~\cite{TARA81} obtained a characterization of cost matrices where tour costs take two distinct values. We provide a simple alternative characterization of such cost matrices that can be … Read more
A set $S$ of vertices in a digraph $D=(V,A)$ is a kernel if $S$ is independent and every vertex in $V-S$ has an out-neighbor in $S$. We show that there exist $O(n2^{19.1 \sqrt{k}}+n^4)$-time and $O(2^{19.1 \sqrt{k}} k^9 + n^2)$-time algorithms for checking whether a planar digraph $D$ of order $n$ has a kernel with at … Read more
We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the … Read more
We propose a new strategy for solving the non-bijective graph matching problem in model-based pattern recognition. The search for the best correspondence between a model and an over-segmented image is formulated as a combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together … Read more