-
作者：Cifuentes, Diego; Agarwal, Sameer; Parrilo, Pablo A.; Thomas, Rekha R.
作者单位：University System of Georgia; Georgia Institute of Technology; Alphabet Inc.; Google Incorporated; University of Washington; University of Washington Seattle; Massachusetts Institute of Technology (MIT)
摘要：We consider a parametric family of quadratically constrained quadratic programs and their associated semidefinite programming (SDP) relaxations. Given a nominal value of the parameter at which the SDP relaxation is exact, we study conditions (and quantitative bounds) under which the relaxation will continue to be exact as the parameter moves in a neighborhood around the nominal value. Our framework captures a wide array of statistical estimation problems including tensor principal component an...
-
作者：Hirai, Hiroshi; Ikeda, Motoki
作者单位：University of Tokyo
摘要：In this paper, we address the minimum-cost node-capacitated multiflow problem in undirected networks. For this problem, Babenko and Karzanov (JCO 24: 202-228, 2012) showed strong polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in O(mlog(nCD)SF(kn,m,k)) time, where n is the number of nodes, m is the number of edges, k is the number of termina...
-
作者：Faenza, Yuri; Munoz, Gonzalo; Pokutta, Sebastian
作者单位：Columbia University; Universidad de O'Higgins; Zuse Institute Berlin; Technical University of Berlin
摘要：Sparse structures are frequently sought when pursuing tractability in optimization problems. They are exploited from both theoretical and computational perspectives to handle complex problems that become manageable when sparsity is present. An example of this type of structure is given by treewidth: a graph theoretical parameter that measures how tree-like a graph is. This parameter has been used for decades for analyzing the complexity of various optimization problems and for obtaining tracta...
-
作者：Fairbrother, Jamie; Turner, Amanda; Wallace, Stein W.
作者单位：Lancaster University; Norwegian School of Economics (NHH)
摘要：Scenario generation is the construction of a discrete random vector to represent parameters of uncertain values in a stochastic program. Most approaches to scenario generation aredistribution-driven, that is, they attempt to construct a random vector which captures well in a probabilistic sense the uncertainty. On the other hand, aproblem-drivenapproach may be able to exploit the structure of a problem to provide a more concise representation of the uncertainty. In this paper we propose an ana...
-
作者：Klimm, Max; Pfetsch, Marc E.; Raber, Rico; Skutella, Martin
作者单位：Technical University of Berlin; Technical University of Darmstadt
摘要：We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX-hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategy...
-
作者：Jia, Xinrui; Sheth, Kshiteej; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challen...
-
作者：Blekherman, Grigoriy; Madhusudhana, Bharath Hebbe
作者单位：University System of Georgia; Georgia Institute of Technology; University of Munich
摘要：Quantum states are represented by positive semidefinite Hermitian operators with unit trace, known as density matrices. An important subset of quantum states is that of separable states, the complement of which is the subset of entangled states. We show that the problem of deciding whether a quantum state is entangled can be seen as amoment problem in real analysis. Only a small number of such moments are accessible experimentally, and so in practice the question of quantum entanglement of a m...
-
作者：Garatti, S.; Campi, M. C.
作者单位：Polytechnic University of Milan; University of Brescia
摘要：Scenario optimization is a broad methodology to perform optimization based on empirical knowledge. One collects previous cases, called scenarios, for the set-up in which optimization is being performed, and makes a decision that is optimal for the cases that have been collected. For convex optimization, a solid theory has been developed that provides guarantees of performance, and constraint satisfaction, of the scenario solution. In this paper, we open a new direction of investigation: the ri...
-
作者：Bolusani, Suresh; Ralphs, Ted K.
作者单位：Lehigh University
摘要：We describe a framework for reformulating and solving optimization problems that generalizes the well-known framework originally introduced by Benders. We discuss details of the application of the procedures to several classes of optimization problems that fall under the umbrella of multilevel/multistage mixed integer linear optimization problems. The application of this abstract framework to this broad class of problems provides new insights and a broader interpretation of the core ideas, esp...
-
作者：Wiebe, J.; Cecilio, I; Dunlop, J.; Misener, R.
作者单位：Imperial College London; Schlumberger
摘要：Optimization problems with uncertain black-box constraints, modeled by warped Gaussian processes, have recently been considered in the Bayesian optimization setting. This work considers optimization problems with aggregated black-box constraints. Each aggregated black-box constraint sums several draws from the same black-box function with different decision variables as arguments in each individual black-box term. Such constraints are important in applications where, e.g., safety-critical meas...
