-
作者：Atamturk, Alper; Narayanan, Vishnu
作者单位：University of California System; University of California Berkeley; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
摘要：Using polarity, we give an outer polyhedral approximation for the epigraph of set functions. For a submodular function, we prove that the corresponding polar relaxation is exact; hence, it is equivalent to the Lovasz extension. The polar approach provides an alternative proof for the convex hull description of the epigraph of a submodular function. Computational experiments show that the inequalities from outer approximations can be effective as cutting planes for solving submodular as well as...
-
作者：Stozhkov, Vladimir; Buchanan, Austin; Butenko, Sergiy; Boginski, Vladimir
作者单位：Oklahoma State University System; Oklahoma State University - Stillwater; Texas A&M University System; Texas A&M University College Station; State University System of Florida; University of Central Florida
摘要：The celebrated Motzkin-Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Turan's theorem in graph theory, but was later used to develop competitive algorithms for the maximum clique problem based on continuous optimization. Clique relaxations, such ass-defective clique ands-plex, emerged a...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：Munoz, Gonzalo; Serrano, Felipe
作者单位：Universidad de O'Higgins; Zuse Institute Berlin
摘要：The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a simplicial conic relaxation of S and an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. However, maximality can be a challenging goal in general. In this work, we sh...
-
作者：Lendl, Stefan; Peis, Britta; Timmermans, Veerle
作者单位：University of Graz; Graz University of Technology; RWTH Aachen University
摘要：Given two matroids M-1 = (E, B-1) and M-2 = (E, B-2) on a common ground set E with base sets B-1 and B-2, some integer k is an element of N, and two cost functions c(1), c(2) : E -> R, we consider the optimization problem to find a basis X is an element of B-1 and a basis Y is an element of B-2 minimizing the cost Sigma(e is an element of X) c(1)(e) + Sigma(e is an element of Y) c(2)(e) subject to either a lower bound constraint | X boolean AND Y| <= k, an upper bound constraint | X boolean AN...
-
作者：Conforti, Michele; Fiorini, Samuel; Huynh, Tony; Weltge, Stefan
作者单位：University of Padua; Universite Libre de Bruxelles; Monash University; Technical University of Munich
摘要：Let G be an n-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maximum weight stable set in G in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-O(n(2)) extended formulation for the stable set polytope of G.
