-
作者：Husic, Edin; Koh, Zhuan Khye; Loho, Georg; Vegh, Laszlo A.
作者单位：Universita della Svizzera Italiana; University of Twente; University of London; London School Economics & Political Science
摘要：A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is at least 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepa...
-
作者：Basu, Amitabh; Jiang, Hongyi; Kerger, Phillip; Molinaro, Marco
作者单位：Johns Hopkins University; Cornell University; Microsoft; Pontificia Universidade Catolica do Rio de Janeiro
摘要：We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. This is derived as a corollary of a more fundamental transfer result that shows how lower bounds on information complexity of continuous convex optimization ...
-
作者：Cela, Eranda; Klinz, Bettina; Lendl, Stefan; Woeginger, Gerhard J.; Wulf, Lasse
作者单位：Graz University of Technology; University of Graz; RWTH Aachen University
摘要：An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best...
-
作者：Nuti, Pranav; Vondrak, Jan
作者单位：Stanford University
摘要：In this paper, we study contention resolution schemes for matchings. Given a fractional matching x and a random set R(x) where each edge e appears independently with probability xe\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_e$$\end{document}, we want to select a matching M subset of R(x)\documentclass[12pt]{m...
-
作者：Altschuler, Jason M.; Parrilo, Pablo A.
作者单位：University of Pennsylvania; Massachusetts Institute of Technology (MIT)
摘要：We provide a concise, self-contained proof that the Silver Stepsize Schedule proposed in our companion paper directly applies to smooth (non-strongly) convex optimization. Specifically, we show that with these stepsizes, gradient descent computes an epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon...
-
作者：Banholzer, Dirk; Fliege, Joerg; Werner, Ralf
作者单位：University of Southampton; University of Augsburg
摘要：We present a novel response surface method for global optimisation of an expensive and noisy (black-box) objective function, where error bounds on the deviation of the observed noisy function values from their true counterparts are available. The method is based on Gutmann's well-established RBF method for minimising an expensive and deterministic objective function, which has become popular both from a theoretical and practical perspective. To construct suitable radial basis function approxim...
-
作者：Hu, Shenglong; Sun, Defeng; Toh, Kim-Chuan
作者单位：National University of Defense Technology - China; Hong Kong Polytechnic University; National University of Singapore
摘要：In this paper, we present a method to certify the approximation quality of a low rank tensor to a given third order symmetric tensor. Under mild assumptions, best low rank approximation is attained if a control parameter is zero or quantified quasi-optimal low rank approximation is obtained if the control parameter is positive. This is based on a primal-dual method for computing a low rank approximation for a given tensor. The certification is derived from the global optimality of the primal a...
-
作者：Giang-Tran, Khanh-Hung; Ho-Nguyen, Nam; Lee, Dabeen
作者单位：University of Sydney; Cornell University; Korea Advanced Institute of Science & Technology (KAIST)
摘要：When faced with multiple minima of an inner-level convex optimization problem, the convex bilevel optimization problem selects an optimal solution which also minimizes an auxiliary outer-level convex objective of interest. Bilevel optimization requires a different approach compared to single-level optimization problems since the set of minimizers for the inner-level objective is not given explicitly. In this paper, we propose a new projection-free conditional gradient method for convex bilevel...
-
作者：Buesing, Christina; Gersing, Timo; Koster, Arie M. C. A.
作者单位：RWTH Aachen University; RWTH Aachen University Hospital; RWTH Aachen University
摘要：Robust combinatorial optimization with budgeted uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when solving robust integer problems, in particular due to its weak linear relaxation. To overc...
-
作者：Cardinal, Jean; Steiner, Raphael
作者单位：Universite Libre de Bruxelles; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless P=NP, there is no polynomial-time algorithm that computes a path of constant length between two vertices at distance two of the perfect matching polytope of a bipartite graph. Conditioned on P not equal NP, this disproves a conjecture by Ito et al. (SIAM J Discrete Math 36(2):1102-1123, 2022). Assuming the Exponential Time Hypothesis we prove ...
