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.

In this paper, I first prove an integral representation theorem: Every quasi-integral on a Stone lattice can be represented by a unique upper-continuous capacity. I then apply this representation theorem to study the topological structure of the space of all upper-continuous capacities on a...

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

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.

Given a network, the facility location problem consists of locating a set of sites on the network to serve existing clients so as to minimize its total cost. Special cases include the simple plant location problem (SPLP), bank account location, p-facility location, and p-median problem.

We describe an @( n^4 h min{log U, n^2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds-Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails...

We study a family of unbounded polyhedra arising in the study of uncapacitated lot-sizing problems with Wagner-Whitin costs. With n the number of periods, we completely characterize the bounded faces of maximal dimension, and derice an O(n^2) alogorithm to express within the polyhedron as a...

The critical role of free entry to correct inherent deviance behavior has been stressed by Vanek (1970), Meade (1972) amongst others. The equivalence theorem (Dreze 1976) defines that labour and entrepreneurial management both lead to the same Pareto optimal equilibrium provided that there is...

In Van den Akker, Van Hoesel, and Savelsbergh (1994), we have studied a time-indexed formulation for single-machine scheduling problems and have presented a complete characterization of all facet inducing inequalities with right-hand side 1 and 2 for the convex hull of the monotone extension of...