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.

Adaptive Polar Sampling (APS) is proposed as a Markov chain Monte Carlo method for Bayesian analysis of models with ill-behaved posterior distributions. In order to sample efficiency from such a distribution, location-scale transformation and a transformation to polar coordinates are used.

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...

We study the polytopes of binary n-strings that encode (positive) integers that are not divisible by a partivular positive integer p - the indivisibility polytopes, as well as the more general "clipped cubes". Also, we discuss a potential application to factoring. Finally, we present some...

This paper considers GMM estimation of autoregressive processes. It is shown that, contrary to the case where the noise is independent, using high-order moments can provide subtantial efficiency gains for estimating the AR model when the noise is only uncorrelated.

This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing,...

This survey paper prepared for the Handbook of Utility Theory covers the axiomatic foundation of decision making under uncertainty when conditional preferences are allowed to be state dependent, leading to an expected state-dependent utility representation.

We extend Kohlberg and Mertens' (1986) structure theorem concerning the Nash equilibrium correspondence to show that its graph is not only homeomorphic to the underlying space of games but that it is also unknotted. This is then shown to have some basic consequences for dynamics whose rest...