-
作者：Dadush, Daniel; Eisenbrand, Friedrich; Rothvoss, Thomas
作者单位：Centrum Wiskunde & Informatica (CWI); Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Washington; University of Washington Seattle
摘要：Approximate integer programming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 . (K-c)+c which is K, scaled by 2 from its center of gravity c. Approximate integer programming can be solved in time 2(O(n)) while the fastest known methods for exact integer programming run in time 2(O(n)) . n(n). So far, there are no efficient methods for integer programming known that are based on appr...
-
作者：Gerstbrein, Matthew; Sanita, Laura; Verberk, Lucy
作者单位：University of Waterloo; Bocconi University; Eindhoven University of Technology
摘要：An edge-weighted, vertex-capacitated graph G is called stable if the value of a maximum-weight capacity-matching equals the value of a maximum-weight fractional capacity-matching. Stable graphs play a key role in characterizing the existence of stable solutions for popular combinatorial games that involve the structure of matchings in graphs, such as network bargaining games and cooperative matching games. The vertex-stabilizer problem asks to compute a minimum number of players to block (i.e....
-
作者：Zheng, Da Wei; Henzinger, Monika
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Institute of Science & Technology - Austria
摘要：We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1-epsilon)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time O(m epsilon(-1)), beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM '14] that runs in O(m epsilon(-1)log epsilon(-1)). Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a (1-epsilon)-approxim...
-
作者：Brun, Matthew; Perini, Tyler; Sinha, Saumya; Schaefer, Andrew J.
作者单位：Massachusetts Institute of Technology (MIT); University of Minnesota System; University of Minnesota Twin Cities; Rice University
摘要：This paper investigates the potential of Lagrangian relaxations to generate quality bounds on non-dominated images of multiobjective integer programs (MOIPs). Under some conditions on the relaxed constraints, we show that a set of Lagrangian relaxations can provide bounds that coincide with every bound generated by the convex hull relaxation. We also provide a guarantee of the relative quality of the Lagrangian bound at unsupported solutions. These results imply that, if the relaxed feasible r...
-
作者：Marumo, Naoki; Takeda, Akiko
作者单位：University of Tokyo; RIKEN
摘要：We propose a new first-order method for minimizing nonconvex functions with Lipschitz continuous gradients and H & ouml;lder continuous Hessians. The proposed algorithm is a heavy-ball method equipped with two particular restart mechanisms. It finds a solution where the gradient norm is less than epsilon \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\od...
-
作者：Laemmel, Sebastian; Shikhman, Vladimir
作者单位：Technische Universitat Chemnitz
摘要：We extend the convergence analysis of the Scholtes-type regularization method for cardinality-constrained optimization problems. Its behavior is clarified in the vicinity of saddle points, and not just of minimizers as it has been done in the literature before. This becomes possible by using as an intermediate step the recently introduced regularized continuous reformulation of a cardinality-constrained optimization problem. We show that the Scholtes-type regularization method is well-defined ...
-
作者：Wang, Alex L.; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University; Purdue University System; Purdue University
摘要：This paper introduces a new storage-optimal first-order method, CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the exact QMP-like SDPs, is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. Crucially, we show how to use a certificate of strict complementarity to construct a low-dimensiona...
-
作者：Wang, Ruodu; Zhang, Zhenyuan
作者单位：University of Waterloo; Stanford University
摘要：We introduce the framework of quadratic-form optimal transport (QOT), whose transport cost has the form integral integral cd pi circle times d pi for some coupling pi between two marginals. Interesting examples of quadratic-form transport cost and their optimization include inequality measurement, the variance of a bivariate function, covariance, Kendall's tau, the Gromov-Wasserstein distance, quadratic assignment problems, and quadratic regularization of classic optimal transport. QOT leads t...
-
作者：Chizat, Lenaic; Delalande, Alex; Vaskevicius, Tomas
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study the convergence rate of Sinkhorn's algorithm for solving entropy-regularized optimal transport problems when at least one of the probability measures, mu, admits a density over R-d. For a semi-concave cost function bounded by cand a regularization parameter lambda > 0, we obtain exponential convergence guarantees on the dual sub-optimality gap with contraction rates that are polynomial in lambda/c(infinity). This represents an exponential improvement over the known contraction rate 1-...
-
作者：Lozano, Leonardo; Borrero, Juan S.
作者单位：University System of Ohio; University of Cincinnati; State University System of Florida; University of South Florida
摘要：We study a class of decision-making problems under uncertainty, where the planner hedges against the worst-case realization in an integer uncertainty set that has a functional dependence on the decisions of the planner. We propose three methods to reformulate and solve these problems: the first is based on a single-level 'semi-infinite' reformulation, where the dependence of the uncertainty on the decisions is modeled with auxiliary binary variables; the second is based on a single-follower bi...
