-
作者：Bagaria, Vivek; Ding, Jian; Tse, David; Wu, Yihong; Xu, Jiaming
作者单位：Stanford University; University of Pennsylvania; Yale University; Duke University
摘要：We introduce the problem of hidden Hamiltonian cycle recovery, where there is an unknown Hamiltonian cycle in an n-vertex complete graph that needs to be inferred from noisy edge measurements. The measurements are independent and distributed according to P-n for edges in the cycle and Q(n) otherwise. This formulation is motivated by a problem in genome assembly, where the goal is to order a set of contigs (genome subsequences) according to their positions on the genome using long-range linking...
-
作者：Russo, Daniel
作者单位：Columbia University
摘要：This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. This paper proposes three simple and intuitive Bayesian algorithms for adaptively allocating measurement effort and formalizes a sense in which these seemingly n...
-
作者：Chen, Mingliu; Sun, Peng; Xiao, Yongbo
作者单位：Duke University; Tsinghua University
摘要：Consider a setting in which a principal induces effort from an agent to reduce the arrival rate of a Poisson process of adverse events. The effort is costly to the agent and unobservable to the principal unless the principal is monitoring the agent. Monitoring ensures effort but is costly to the principal. The optimal contract involves monetary payments and monitoring sessions that depend on past arrival times. We formulate the problem as a stochastic optimal control model and solve the proble...
-
作者：Ashlagi, Itai; Saberi, Amin; Shameli, Ali
作者单位：Stanford University
摘要：We generalize the serial dictatorship (SD) and probabilistic serial (PS) mechanism for assigning indivisible objects (seats in a school) to agents (students) to accommodate distributional constraints. Such constraints are motivated by equity considerations. Our generalization of SD maintains several of its desirable properties, including strategyproofness, Pareto optimality, and computational tractability, while satisfying the distributional constraints with a small error. Our generalization o...
-
作者：Wang, Jinting; Wang, Zhongbin; Liu, Yunan
作者单位：Central University of Finance & Economics; Nankai University; Beijing Jiaotong University; North Carolina State University
摘要：In this article, we introduce a service grade differentiation policy for queueing models with customer retrials. We show that the average waiting time can be reduced through strategically allocating the rates of service and retrial times without needing additional service capacity. Countering to the intuition that higher service variability usually yields a larger delay, we show that the benefits of our simultaneous service-and-retrial differentiation policy outweigh the impact of the increase...
-
作者：Modaresi, Sajad; Saure, Denis; Vielma, Juan Pablo
作者单位：University of North Carolina; University of North Carolina Chapel Hill; Universidad de Chile; Massachusetts Institute of Technology (MIT)
摘要：We study dynamic decision making under uncertainty when, at each period, a decision maker implements a solution to a combinatorial optimization problem. The objective coefficient vectors of said problem, which are unobserved before implementation, vary from period to period. These vectors, however, are known to be random draws from an initially unknown distribution with known range. By implementing different solutions, the decision maker extracts information about the underlying distribution b...
-
作者：Hassin, Refael; Snitkovsky, Ran I.
作者单位：Tel Aviv University
摘要：Naor's celebrated paper studies customer decisions in an observable M/M/1 queue in which joining-customers utility is linearly decreasing with the joining position. Naor derives the optimal threshold strategies for the individuals, social planner, and monopolist and proves that the monopoly optimal threshold is (weakly) smaller than the socially optimal threshold, which is (weakly) smaller than the individually optimal one. Studies show, based on numerical observations and/or ad hoc proof tech...
-
作者：Bertazzi, Luca; Secomandi, Nicola
作者单位：University of Brescia; Carnegie Mellon University
摘要：The extant literature on the vehicle routing problem with stochastic demands indicates that the restocking strategy yields moderate percentage expected cost reductions relative to the a priori approach but lacks theoretical support for this improvement. We conduct a worst-case analysis that corroborates the observed restocking benefits and enhances our understanding of a foundational model in logistics under uncertainty.
-
作者：Zhang, Heng; Rusmevichientong, Paat; Topaloglu, Huseyin
作者单位：University of Southern California
摘要：We consider uncapacitated and capacitated assortment problems under the paired combinatorial logit model, where the goal is to find a set of products to offer to maximize the expected revenue obtained from a customer. In the uncapacitated setting, we can offer any set of products, whereas in the capacitated setting, there is an upper bound on the number of products that we can offer. We establish that even the uncapacitated assortment problem is strongly NP-hard. To develop an approximation fr...
-
作者：Clarkson, Jake; Glazebrook, Kevin D.; Lin, Kyle Y.
作者单位：Lancaster University; Lancaster University; United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：An object is hidden in one of several discrete locations according to some known probability distribution, and the goal is to discover the object in the minimum expected time by successive searches of individual locations. If there is only one way to search each location, this search problem is solved using Gittins indices. Motivated by modern search technology, we extend earlier work to allow two modes-fast and slow-to search each location. The fast mode takes less time, but the slow mode is ...
