-
作者：Candogan, Ozan; Ozdaglar, Asuman; Parrilo, Pablo A.
作者单位：University of Chicago; Massachusetts Institute of Technology (MIT)
摘要：We study a special class of multi-item valuations (tree valuations) that exhibit both value complementarity and substitutability. We provide a linear programming formulation of the efficient allocation problem that is of polynomial size in the number of agents and items. This reveals a new class of valuations for which a Walrasian equilibrium exists in the presence of value complementarities. An iterative algorithm for this linear program, in conjunction with an appropriate payment rule, yield...
-
作者：Jasin, Stefanus
作者单位：University of Michigan System; University of Michigan
摘要：We consider a standard network revenue management (RM) problem and study the performance of a linear program (LP)-based control, the Probabilistic Allocation Control (PAC), in the presence of unknown demand parameters. We show that frequent re-optimizations of PAC without re-estimation suffice to shrink the asymptotic impact of estimation error on revenue loss. If, in addition to re-optimizations, we also frequently re-estimate the parameters, we prove that the performance of PAC in the unknow...
-
作者：Jasin, Stefanus; Sinha, Amitabh
作者单位：University of Michigan System; University of Michigan
摘要：We consider an online multi-item retailer with multiple fulfillment facilities and finite inventory. The challenge faced by the retailer is to construct a fulfillment policy to decide from which facility each of the items in the arriving order should be fulfilled, in a way that minimizes the expected total shipping costs of fulfilling customer orders over a finite horizon. Shipping costs are linear in the size of the package shipped as well as the distance from the facility to the customer. We...
-
作者：Green, Alex E. S.; Green, Deborah S.; Francis, Richard L.
作者单位：State University System of Florida; University of Florida; State University System of Florida; University of Florida
摘要：Alex Green was a pioneering operations analyst/researcher for the U.S. Army Air Force during World War II. His February 1945 operations analysis Report on the Combat Performance of the Remote Control Turrets of B-29 Aircraft was classified and buried for 70 years. Stationed in the China-Burma-India theatre and addressing a problem of combat losses posed by General Curtis LeMay, Green used written reports and interviews to draw conclusions regarding direction of enemy attack on the B-29s, oppos...
-
作者：Barrera, Jorge; Garcia, Alfredo
作者单位：University of Virginia; State University System of Florida; University of Florida
摘要：We consider the problem of efficiently allocating the capacity of a number of service facilities (prone to congestion) to a set of users with private information regarding their willingness to pay for different combinations of throughput versus latency. Auction mechanisms can be used to schedule the service capacity of available facilities. However, the interdependency of users' valuations implies that simple uniform price adjustment processes (e.g., tatonnement) either fail to effectively cle...
-
作者：Celik, Melih; Ergun, Ozlem; Keskinocak, Pinar
作者单位：Middle East Technical University; Northeastern University; University System of Georgia; Georgia Institute of Technology
摘要：Debris management is one of the most time consuming and complicated activities among post-disaster operations. Debris clearance is aimed at pushing the debris to the sides of the roads so that relief distribution and search-and-rescue operations can be maintained in a timely manner. Given the limited resources, uncertainty, and urgency during disaster response, efficient and effective planning of debris clearance to achieve connectivity between relief demand and supply is important. In this pa...
-
作者：Doan, Xuan Vinh; Li, Xiaobo; Natarajan, Karthik
作者单位：University of Warwick; University of Warwick; University of Minnesota System; University of Minnesota Twin Cities; Singapore University of Technology & Design
摘要：In this paper, we develop a distributionally robust portfolio optimization model where the robustness is across different dependency structures among the random losses. For a Frechet class of discrete distributions with overlapping marginals, we show that the distributionally robust portfolio optimization problem is efficiently solvable with linear programming. To guarantee the existence of a joint multivariate distribution consistent with the overlapping marginal information, we make use of a...
-
作者：Azar, Yossi; Fleischer, Lisa; Jain, Kamal; Mirrokni, Vahab; Svitkina, Zoya
作者单位：Tel Aviv University; Dartmouth College; Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated
摘要：We investigate the influence of different algorithmic choices on the approximation ratio in selfish scheduling. Our goal is to design local policies that minimize the inefficiency of resulting equilibria. In particular, we design optimal coordination mechanisms for unrelated machine scheduling, and improve the known approximation ratio from Theta(m) to Theta(log m), where m is the number of machines. A local policy for each machine orders the set of jobs assigned to it only based on parameters...
-
作者：Lamorgese, Leonardo; Mannino, Carlo
作者单位：SINTEF
摘要：Trains' movements on a railway network are regulated by official timetables. Deviations and delays occur quite often in practice, demanding fast rescheduling and rerouting decisions in order to avoid conflicts and minimize overall delay. This is the real-time train dispatching problem. In contrast with the classic holistic approach, we show how to decompose the problem into smaller subproblems associated with the line and the stations. This decomposition is the basis for a master-slave solutio...
-
作者：Sandholm, Tuomas; Likhodedov, Anton
作者单位：Carnegie Mellon University; Deutsche Bank
摘要：Designing optimal-that is, revenue-maximizing-combinatorial auctions (CAs) is an important elusive problem. It is unsolved even for two bidders and two items for sale. Rather than pursuing the manual approach of attempting to characterize the optimal CA, we introduce a family of CAs and then seek a high-revenue auction within that family. The family is based on bidder weighting and allocation boosting; we coin such CAs virtual valuations combinatorial auctions (VVCAs). VVCAs are the Vickrey-Cl...
