We apply theta body relaxations to the $K_i$ cover problem and use this to show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where all $K_i$-$p$-hole facets are valid, addressing an open question of Conforti et al \cite{conforti}. For the triangle free problem, we show for $K_n$ that … Read more
In this paper, we establish hardness and approximation results for various $L_p$-ball constrained homogeneous polynomial optimization problems, where $p \in [2,\infty]$. Specifically, we prove that for any given $d \ge 3$ and $p \in [2,\infty]$, both the problem of optimizing a degree-$d$ homogeneous polynomial over the $L_p$-ball and the problem of optimizing a degree-$d$ multilinear … Read more
In this paper we consider $l_0$ regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving $l_0$ regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the … Read more
In this paper we discuss multistage programming with the data process subject to uncertainty. We consider a situation were the data process can be naturally separated into two components, one can be modeled as a random process, with a specified probability distribution, and the other one can be treated from a robust (worst case) point … Read more
We show that for continuous time dynamical systems described by polynomial differential equations of modest degree (typically equal to three), the following decision problems which arise in numerous areas of systems and control theory cannot have a polynomial time (or even pseudo-polynomial time) algorithm unless P=NP: local attractivity of an equilibrium point, stability of an … Read more
This paper addresses law invariant coherent risk measures and their Kusuoka representations. By elaborating the existence of a minimal representation we show that every Kusuoka representation can be reduced to its minimal representation. Uniqueness — in a sense specified in the paper — of the risk measure’s Kusuoka representation is derived from this initial result. … Read more
The past decade has seen advances in general methods for symmetry breaking in mixed-integer linear programming. These methods are advantageous for general problems with general symmetry groups. Some important classes of MILP problems, such as bin packing and graph coloring, contain highly structured symmetry groups. This observation has motivated the development of problem-specific techniques. In … Read more
The planning of chemical production often involves the optimization of the size of the tasks to be performed subject to unit capacity constraints, as well as inventory constraints for intermediate materials. While several mixed-integer programming (MIP) models have been proposed that account for these features, the development of tightening methods for these formulations has received … Read more
We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem. Article Download View Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. II. The Unimodular Two-Dimensional Case
One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast First Order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when … Read more