On the Complexity of Nonoverlapping Multivariate Marginal Bounds for Probabilistic Combinatorial Optimization Problems

References

• Agarwal A., Zolotov V., Blaauw D. T. Statistical timing analysis using bounds and selective enumeration. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (2003) 22(9):1243–1260Crossref, Google Scholar
• Ball M. O., Colbourn C. J., Provan J. S., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Network reliability. Network Models (1995) 7(Elsevier Science, Amsterdam) 673–762Handbooks in Operations Research and Management ScienceCrossref, Google Scholar
• Bean J. C. A Lagrangian algorithm for the multiple choice integer program. Oper. Res. (1984) 32(5):1185–1193Link, Google Scholar
• Bertsimas D., Natarajan K., Teo C. P. Probabilistic combinatorial optimization: Moments, semidefinite programming and asymptotic bounds. SIAM J. Optim. (2004) 15(1):185–209Crossref, Google Scholar
• Bertsimas D., Natarajan K., Teo C. P. Persistence in discete optimization under data uncertainty. Math. Programming (2006) 108(2–3):251–274Crossref, Google Scholar
• Birge J. R., Maddox M. J. Bounds on expected project tardiness. Oper. Res. (1995) 43(5):838–850Link, Google Scholar
• Blaauw D. T., Chopra K., Srivastava A., Scheffer L. Statistical timing analysis: From basic principles to state of the art. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (2008) 27(4):589–607Crossref, Google Scholar
• Dodin B. Bounding the project completion time distribution in PERT networks. Oper. Res. (1985) 33(4):862–881Link, Google Scholar
• Dudzinski K., Walukiewicz S. Exact methods for the knapsack problem and its generalizations. Eur. J. Oper. Res. (1987) 28(1):3–21Crossref, Google Scholar
• Embrechts P., Pucetti G. Bounds for functions of multivariate risks. J. Multivariate Anal. (2006) 97(2):526–547Crossref, Google Scholar
• Fulkerson D. R. Expected critical path length in PERT networks. Oper. Res. (1962) 10(6):808–817Link, Google Scholar
• Genest C., Quesada Molina J. J., Rodríguez Lallena J. A. De l'impossibilité de construire des lois à marges multidimensionnelles données à partir de copules. Comptes rendus de l'Académie des sciences de Paris (1995) 320(6):723–726Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1988) 2(Springer-Verlag, Berlin) Crossref, Google Scholar
• Hagstrom J. N. Computational complexity of PERT problems. Networks (1988) 18(2):139–147Crossref, Google Scholar
• Kirkpatrick T., Clark N. PERT as an aid to logic design. IBM J. Res. Development (1966) 10(2):135–141Crossref, Google Scholar
• Kleindorfer G. B. Bounding distributions for a stochastic acyclic network. Oper. Res. (1971) 19(7):1586–1601Link, Google Scholar
• Klein Hanevel W. K. Robustness against dependence in PERT: An application of duality and distributions with known marginals. Math. Programming Stud. (1986) 27:153–182Crossref, Google Scholar
• Lai T. L., Robbins H. Maximally dependent random variables. Proc. Natl. Acad. Sci. USA (1976) 73(2):286–288Crossref, Google Scholar
• Li H., Scarsini M., Shaked M., Rüschendorf L., Schweizer B., Taylor M. D. Bounds for the distribution of a multivariate sum. Distributions with Fixed Marginals and Related Topics (1996a) 28(Institute of Mathematical Statistics, Hayward, CA) 198–212IMS Lecture NotesCrossref, Google Scholar
• Li H., Scarsini M., Shaked M. Linkages: A tool for the construction of multivariate distributions with given nonoverlapping multivariate marginals. J. Multivariate Anal. (1996b) 56(1):20–41Crossref, Google Scholar
• McNeil A. J., Frey R., Embrechts P.Quantitative Risk Management: Concepts, Techniques and Tools (2005) (Princeton University Press, Princeton, NJ) Princeton Series in FinanceGoogle Scholar
• Meilijson I. Sharp bounds on the largest of some linear combinations of random variables with given marginal distributions. Probab. Engrg. Informational Sci. (1991) 5(1):1–14Crossref, Google Scholar
• Meilijson I., Nadas A. Convex majorization with an application to the length of critical path. J. Appl. Probab. (1979) 16(3):671–677Crossref, Google Scholar
• Möhring R. H., Alt H. Scheduling under uncertainty: Bounding the makespan distribution. Computational Discrete Mathematics: Advanced Lectures (2001) 2122(Springer, Berlin) 79–97Lecture Notes in Computer ScienceCrossref, Google Scholar
• Möhring R. H., Radermacher F. J., Slowiński R., Wegarlz J. The order-theoretic approach to scheduling: The stochastic case. Advances in Project Scheduling (1989) (Elsevier, Amsterdam) 479–531IMS Lecture NotesCrossref, Google Scholar
• Nadas A. Probabilistic PERT. IBM J. Res. Development (1979) 23(3):339–347Crossref, Google Scholar
• Natarajan K., Song M., Teo C.-P. Persistency model and its applications in choice modeling. Management Sci. (2009) 55(3):453–469Link, Google Scholar
• Provan J. S., Ball M. O. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. (1983) 12(4):777–788Crossref, Google Scholar
• Ringer L. J. A statistical theory for PERT in which completion times of activities are inter-dependent. Management Sci. (1971) 17(11):717–723Link, Google Scholar
• Rüschendorf L. Solution of statistical optimization problem by rearrangement methods. Metrika (1983) 30:55–61Crossref, Google Scholar
• Rüschendorf L. Comparison of multivariate risks and positive dependence. J. Appl. Probab. (2004) 41(2):391–406Crossref, Google Scholar
• Sapatnekar S.Timing (2004) (Kluwer Academic Publishers, Boston) Google Scholar
• Scarsini M. Copulae of probability measures on product spaces. J. Multivariate Anal. (1989) 31(2):201–219Crossref, Google Scholar
• Shogan A. W. Bounding distributions for a stochastic PERT network. Networks (1983) 12(4):777–788Google Scholar
• Sklar A. Fonctions de répartition à n dimensions et leurs marges. Publications de l'Institut de Statistique de l'Université de Paris (1959) 8:229–231Google Scholar
• Spelde H. G. Stochastische Netzpläne und ihre Anwendungim Baubetrieb. (1976) . Ph.D. thesis, Rheinisch-Westfälische Technische Hochschule, Aachen, GermanyGoogle Scholar
• Valiant L. G. The complexity of enumeration and reliability problems. SIAM J. Comput. (1979) 8(3):410–421Crossref, Google Scholar
• van Dorp J. R., Duffey M. R. Statistical dependence in risk analysis for project networks using Monte Carlo methods. Internat. J. Production Econom. (1999) 58(1):17–29Crossref, Google Scholar
• Visweswariah C., Ravindran K., Kalafala K., Walker S. G., Narayan S., Beece D. K., Piaget J., Venkateswaran N., Hemmett J. G. First-order incremental block-based statistical timing analysis. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (2006) 25(10):2170–2179Crossref, Google Scholar
• Weiss G. Stochastic bounds on distributions of optimal value functions with applications to PERT, network flows and reliability. Oper. Res. (1986) 34(4):595–605Link, Google Scholar
• Wollmer R. D. Critical path planning under uncertainty. Math. Programming Stud. (1985) 25:164–171Crossref, Google Scholar