-
作者：Tien-Son Pham
作者单位：Ton Duc Thang University; Ton Duc Thang University
摘要：In this paper we study necessary optimality conditions for the problem of minimizing a polynomial function over a set defined by polynomial inequalities. Assume that the problem is bounded below and has the Mangasarian-Fromovitz property at infinity. We first show that if the problem does not have an optimal solution, then a version at infinity of the Fritz John optimality conditions holds. From this we derive a version at infinity of the Karush-Kuhn-Tucker optimality conditions. As applicatio...
-
作者：Buchbinder, Niv; Feldman, Moran
作者单位：Tel Aviv University; Open University Israel
摘要：The study of combinatorial optimization problems with submodular objectives has attracted much attention in recent years. Such problems are important in both theory and practice because their objective functions are very general. Obtaining further improvements for many submodular maximization problems boils down to finding better algorithms for optimizing a relaxation of them known as the multilinear extension. In this work, we present an algorithm for optimizing the multilinear relaxation who...
-
作者：Frazier, Peter, I; Henderson, Shane G.; Waeber, Rolf
作者单位：Cornell University
摘要：The probabilistic bisection algorithm (PBA) solves a class of stochastic root-finding problems in one dimension by successively updating a prior belief on the location of the root based on noisy responses to queries at chosen points. The responses indicate the direction of the root from the queried point and are incorrect with a fixed probability. The fixed-probability assumption is problematic in applications, and so we extend the PBA to apply when this assumption is relaxed. The extension in...
-
作者：Bazzi, Abbas; Fiorini, Samuel; Pokutta, Sebastian; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universite Libre de Bruxelles; University System of Georgia; Georgia Institute of Technology
摘要：The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349] proved that the problem is NP-hard to approximate within a factor 2- epsilon, assuming the unique games conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inappr...
-
作者：Kang, Wanmo; Lee, Jong Mun
作者单位：Korea Advanced Institute of Science & Technology (KAIST)
摘要：In this paper, we propose unbiased sensitivity estimators of the expected functionals of one-dimensional diffusion processes. Under general diffusion models, it is common to rely on discretization methods such as the Euler scheme for the generation of sample paths because of the lack of knowledge in the probability distributions associated with the diffusions. The Euler discretization method is easy to apply, but it is difficult to avoid discretization biases. As an alternative approach, we pr...
-
作者：Li, Jian; Deshpande, Amol
作者单位：Tsinghua University; University System of Maryland; University of Maryland College Park
摘要：We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input data set are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, minimum weight matchings, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk-averse or risk-prone behaviors, and, instead, we consider a more general objective, which is to max...
-
作者：Schied, Alexander; Zhang, Tao
作者单位：University of Waterloo; University of Mannheim
摘要：We consider a Nash equilibrium between two high-frequency traders (HFTs) in a simple market impact model with transient price impact and additional quadratic transaction costs. We prove existence and uniqueness of the Nash equilibrium and show that, for small transaction costs, the HFTs engage in a hot potato game, in which the same asset position is sold back and forth. We then identify a critical value for the size of the transaction costs above, for which all oscillations disappear and stra...
-
作者：Ahmadi, Amir Ali; Hall, Georgina
作者单位：INSEAD Business School
摘要：In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellensatze from the late 20th century (e.g., due to Stengle, Putinar, or Schmudgen) that certify positivity of a polynomial on an arbitrary closed basic semialgebraic set. In this paper, we show that such hierarchies could in fact be designed fr...
-
作者：Armony, Mor; Atar, Rami; Honnappa, Harsha
作者单位：New York University; Technion Israel Institute of Technology; Purdue University System; Purdue University
摘要：We consider the problem of scheduling appointments for a finite customer population to a service facility with customer no-shows to minimize the sum of customer waiting time and server overtime costs. Because appointments need to be scheduled ahead of time, we refer to this problem as an optimization problem rather than a dynamic control one. We study this optimization problem in fluid and diffusion scales and identify asymptotically optimal schedules in both scales. In fluid scale, we show th...
-
作者：Alaei, Saeed; Fu, Hu; Haghpanah, Nima; Hartline, Jason; Malekian, Azarakhsh
作者单位：Alphabet Inc.; Google Incorporated; University of British Columbia; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Northwestern University; University of Toronto
摘要：We study an optimal auction problem for selecting a subset of agents to receive an item or service, whereby each agent's service can be configured, the agent has multidimensional preferences over configurations, and there is a limit on the number of agents that can be simultaneously served. We give a polynomial time reduction from the multiagent problem to appropriately defined single-agent problems. We further generalize the setting to matroid feasibility constraints and obtain exact and appr...
