In the first part of this paper we prove that the global quadratic optimization problem over a simplex can be solved with a constant relative accuracy. In the second part we consider some natural extensions of the result.

We present a convex conic relaxation for a problem of maximising an indefinite quadratic form over a set of convex constraints on the squared variables. We show that for all these problems we get at least 12/37 relative accuracy of the approximation. In the second part of the paper we derive the...

This paper presents a combinatorial polynomial-time algorithm for minimizing submodular set functions. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter.

The cut polyhedron cut(G) of an undirected graph G = (V,E) is the dominant of the convex hull of all of its nonempty edge cutsets. After examining various compact extended formulations for cut(G), we study some of its polyhedral properties. In particular, we characterize all of the facets...