Differentiability of the Value Function of Nonclassical Optimal Growth Models

We consider an optimal growth (multi-sector) model with nonconvex technology. Using the Clarke results on generalized gradients, we prove that the value function has left and right derivatives with respect to the initial capital stock, without requiring supermodularity assumptions.     

Design of manufacturing systems using queueing models

Design issues in various types of manufacturing systems such as flow lines, automatic transfer lines, job shops, flexible machining systems, flexible assembly systems and multiple cell systems are addressed in this paper. Approaches to resolving these design issues of these systems using queueing models are reviewed. In particular, we show how the structural properties that are recently derived for single and multiple stage queueing systems can be used effectively in the solution of certain design optimization problems.Supported in part by the Natural Sciences and Engineering Research Council of Canada via Operating and Strategic Grants on Modeling and Analyses of Production Systems and Modeling and Implementation of Just-in-Time Cells.Supported in part by the NSF Grants ECS-8811234 and DDM-9113008 and by Sloan Foundation Grants for the Consortium for Competitiveness and Cooperation and for the study on Competitive Semiconductor Manufacturing.     

S-modular games,with queueing applications

The notion ofS-modularity was developed by Glasserman and Yao [9] in the context of optimal control of queueing networks.S-modularity allows the objective function to be supermodular in some variables and submodular in others. It models both compatible and conflicting incentives, and hence conveniently accommodates a wide variety of applications. In this paper, we introduceS-modularity into the context ofn-player noncooperative games. This generalizes the well-known supermodular games of Topkis [22], where each player maximizes a supermodular payoff function (or equivalently, minimizes a submodular payoff function). We illustrate the theory through a variety of applications in queueing systems.Supported in part by NSF Grant MSS-92-16490, and by Columbia's Center for Telecommunications Research.     

Structural results for the control of queueing systems using event-based dynamic programming

In this paper we study monotonicity results for optimal policies of various queueing and resource sharing models. The standard approach is to propagate, for each specific model, certain properties of the dynamic programming value function. We propose a unified treatment of these models by concentrating on the events and the form of the value function instead of on the value function itself. This is illustrated with the systematic treatment of one and two-dimensional models. This revised version was published online in June 2006 with corrections to the Cover Date.     

Recognition problems for special classes of polynomials in 0–1 variables

This paper investigates the complexity of various recognition problems for pseudo-Boolean functions (i.e., real-valued functions defined on the unit hypercubeB ⁿ = {0, 1} ⁿ ), when such functions are represented as multilinear polynomials in their variables. Determining whether a pseudo-Boolean function (a) is monotonic, or (b) is supermodular, or (c) is threshold, or (d) has a unique local maximum in each face ofB ⁿ , or (e) has a unique local maximum inB ⁿ , is shown to be NP-hard. A polynomial-time recognition algorithm is presented for unimodular functions, previously introduced by Hansen and Simeone as a class of functions whose maximization overB ⁿ is reducible to a network minimum cut problem.