-
作者：Chen, Zhi; Sim, Melvyn; Xu, Huan
作者单位：City University of Hong Kong; National University of Singapore; University System of Georgia; Georgia Institute of Technology
摘要：We consider a distributionally robust optimization problem where the ambiguity set of probability distributions is characterized by a tractable conic representable support set and by expectation constraints. We propose a new class of infinitely constrained ambiguity sets for which the number of expectation constraints could be infinite. The description of such ambiguity sets can incorporate the stochastic dominance, dispersion, fourth moment, and our newly proposed entropic dominance informati...
-
作者：Fattahi, Ali; Dasu, Sriram; Ahmadi, Reza
作者单位：University of California System; University of California Los Angeles; University of Southern California
摘要：The nonnegative least-squares (NNLS) problem is defined as finding the Euclidean distance to a convex cone generated by a set of discrete points in R. In this paper, we study NNLS when the discrete points are implicitly known and there are an exponentially large number of them (e.g., the set of integer feasible solutions of a mixed-integer program). This problem is motivated by a large auto manufacturer that produces mass customized products where the products are configured by choosing a subs...
-
作者：Kerstens, Kristiaan; Sadeghi, Jafar; Van de Woestyne, Ignace
作者单位：IESEG School of Management; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Humanities & Social Sciences (INSHS); Kharazmi University; KU Leuven
摘要：The output-oriented plant capacity notion, which has been around for more than two decades, has been empirically applied mainly in the fishery and the hospital sectors. Since its introduction to the literature, a specified problem is that this notion may not be attainable, in that it presupposes potentially unlimited numbers of variable inputs to determine the maximum number of outputs available. However, this lack of attainability has not been explored previously. This paper fills this void b...
-
作者：Balseiro, Santiago R.; Besbes, Omar; Weintraub, Gabriel Y.
作者单位：Columbia University; Stanford University
摘要：We study the dynamic mechanism design problem of a seller who repeatedly auctions independent items over a discrete time horizon to buyers who face a cumulative budget constraint. A driving motivation behind our model is the emergence of real-time bidding markets for online display advertising in which such budgets are prevalent. We assume the seller has a strong form of limited commitment: she commits to the rules of the current auction but cannot commit to those of future auctions. We show t...
-
作者：Berkhout, Joost; Heidergott, Bernd F.
作者单位：Vrije Universiteit Amsterdam
摘要：The research presented in this paper is motivated by the growing interest in the analysis of networks found in the World Wide Web and of social networks. In this paper, we elaborate on the Kemeny constant as a measure of connectivity of the weighted graph associated with a Markov chain. For finite Markov chains, the Kemeny constant can be computed by means of simple algebra via the deviation matrix and the ergodic projector of the chain. Using this fact, we introduce a new decomposition algori...
-
作者：Balseiro, Santiago R.; Brown, David B.
作者单位：Columbia University; Duke University
摘要：In the analysis of complex stochastic dynamic programs, we often seek strong theoretical guarantees on the suboptimality of heuristic policies. One technique for obtaining performance bounds is perfect information analysis: this approach provides bounds on the performance of an optimal policy by considering a decision maker who has access to the outcomes of all future uncertainties before making decisions, that is, fully relaxed nonanticipativity constraints. A limitation of this approach is t...
-
作者：Bertsimas, Dimitris; Delarue, Arthur; Jaillet, Patrick; Martin, Sebastien
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Twenty-first century urban planners have identified the understanding of complex city traffic patterns as a major priority, leading to a sharp increase in the amount and the diversity of traffic data being collected. For instance, taxi companies in an increasing number of major cities have started recording metadata for every individual car ride, such as its origin, destination, and travel time. In this paper, we show that we can leverage network optimization insights to extract accurate trave...
-
作者：Borrero, Juan S.; Prokopyev, Oleg A.; Saure, Denis
作者单位：Oklahoma State University System; Oklahoma State University - Stillwater; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Universidad de Chile
摘要：We present a framework for a class of sequential decision-making problems in the context of general interdiction problems, in which a leader and a follower repeatedly interact. At each period, the leader allocates resources to disrupt the performance of the follower (e.g., as in defender-attacker or network interdiction problems), who, in turn, minimizes some cost function over a set of activities that depends on the leader's decision. Although the follower has complete knowledge of the follow...
-
作者：Cui, Shiliang; Su, Xuanming; Veeraraghavan, Senthil
作者单位：Georgetown University; University of Pennsylvania
摘要：Customers often wait in queues before being served. Because waiting is undesirable, customers may come back later (i.e., retry) when the queue is too long. However, retrial attempts can be costly as a result of transportation fees and service delays. This paper introduces a framework for rational retrial decisions in stationary queues. Our approach accommodates retrials in queues by replicating the Naor's model [Naor P (1969) The regulation of queue size by levying tolls. Econometrica 37(1):15...
-
作者：Hellerstein, Lisa; Lidbetter, Thomas; Pirutinsky, Daniel
作者单位：New York University; New York University Tandon School of Engineering; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick
摘要：We present efficient algorithms for computing optimal or approximately optimal strategies in a zero-sum game for which player I has n pure strategies and player II has an arbitrary number of pure strategies. We assume that for any given mixed strategy of player I, a best response, or approximate best response, of player II can be found by an oracle-in-time polynomial in n. We then show how our algorithms may be applied to several search games with applications to security and counterterrorism....
