-
作者：Neuwohner, Meike
作者单位：University of London; London School Economics & Political Science
摘要：The Maximum Leaf Spanning Arborescence problem (MLSA) in directed acyclic graphs (dags) is defined as follows: Given a directed acyclic graph G and a vertex r is an element of V(G) from which every other vertex is reachable, find a spanning arborescence rooted at r maximizing the number of leaves (vertices with out-degree zero). The MLSAin dags is known to be APX-hard as reported byNadine Schwartges, Spoerhase, andWolff (Approximation and OnlineAlgorithms, Springer, Berlin Heidelberg, 2012) an...
-
作者：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...
-
作者：Gallego, Guillermo; Segev, Danny
作者单位：The Chinese University of Hong Kong, Shenzhen; Tel Aviv University; Tel Aviv University
摘要：In the adaptive ProbeTopK problem, given a collection of mutually independent random variables X1,..., Xn, our goal is to design an adaptive probing policy to sample these variables in a sequence of T stages, with the objective ofmaximizing the expected sum of the K highest rewards sampled. In spite of its stylized formulation, this setting captures numerous technical hurdles inherent to stochastic optimization, related to both information structure and efficient computation. For these reasons...
-
作者：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 ...
