Doan, Xuan Vinh and Natarajan, K. (2012) On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems. Operations Research, Vol.60 (No.1). pp. 138-149. doi:10.1287/opre.1110.1005 ISSN 0030-364X.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

Given a combinatorial optimization problem with an arbitrary partition of the set of random objective coefficients, we evaluate the tightest-possible bound on the expected optimal value for joint distributions consistent with the given multivariate marginals of the subsets in the partition. For univariate marginals, this bound was first proposed by Meilijson and Nadas [Meilijson, I., A. Nadas. 1979. Convex majorization with an application to the length of critical path. J. Appl. Probab. 16(3) 671–677]. We generalize the bound to nonoverlapping multivariate marginals using multiple-choice integer programming. New instances of polynomial-time computable bounds are identified for discrete distributions. For the problem of selecting up to M items out of a set of N items of maximum total weight, the multivariate marginal bound is shown to be computable in polynomial time, when the size of each subset in the partition is O(log N). For an activity-on-arc PERT network, the partition is naturally defined by subsets of incoming arcs into nodes. The multivariate marginal bound on expected project duration is shown to be computable in time polynomial in the maximum number of scenarios for any subset and the size of the network. As an application, a polynomial-time solvable two-stage stochastic program for project crashing is identified. An important feature of the bound developed in this paper is that it is exactly achievable by a joint distribution, unlike many of the existing bounds.

Item Type:	Journal Article
Subjects:	H Social Sciences > HA Statistics
Divisions:	Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School
Journal or Publication Title:	Operations Research
Publisher:	Institute for Operations Research and the Management Sciences (I N F O R M S)
ISSN:	0030-364X
Official Date:	2012
Dates:	Date Event 2012 Published
Volume:	Vol.60
Number:	No.1
Page Range:	pp. 138-149
DOI:	10.1287/opre.1110.1005
Status:	Peer Reviewed
Publication Status:	Published

Request changes or add full text files to a record

Repository staff actions (login required)

View Item