-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：The present work is the first member of a pair of papers concerning decreasingly-minimal (dec-min) elements of a set of integral vectors, where a vector is dec-min if its largest component is as small as possible, within this, the next largest component is as small as possible, and so on. This discrete notion, along with its fractional counterpart, showed up earlier in the literature under various names. The domain we consider is an M-convex set, that is, the set of integral elements of an int...
-
作者：Garg, Naveen; Kumar, Nikhil; Sebo, Andras
作者单位：Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Potsdam; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-multicut-gap. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an...
-
作者：Anegg, Georg; Angelidakis, Haris; Kurpisz, Adam; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Eindhoven University of Technology
摘要：There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints....
-
作者：Driggs, Derek; Ehrhardt, Matthias J.; Schonlieb, Carola-Bibiane
作者单位：University of Cambridge; University of Bath
摘要：Variance reduction is a crucial tool for improving the slow convergence of stochastic gradient descent. Only a few variance-reduced methods, however, have yet been shown to directly benefit from Nesterov's acceleration techniques to match the convergence rates of accelerated gradient methods. Such approaches rely on negative momentum, a technique for further variance reduction that is generally specific to the SVRG gradient estimator. In this work, we show for the first time that negative mome...
-
作者：Friedland, Shmuel; Lasserre, Jean-Bernard; Lim, Lek-Heng; Nie, Jiawang
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Centre National de la Recherche Scientifique (CNRS); University of Chicago; University of California System; University of California San Diego
-
作者：Ahmadi, Amir Ali; Zhang, Jeffrey
作者单位：Princeton University; Carnegie Mellon University
摘要：We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance c(n) (for any constant c >= 0) of a local minimizer of an n-variate quadratic function over a polytope. This result (even with c = 0) answers a question of Pardalos and Vavasis that appeared in 1992 on a list of seven open problems in complexity theory for numerical optimization. Our proof technique also implies that the problem of deciding whether a quadratic function has a local...
-
作者：Erdogdu, Murat A.; Ozdaglar, Asuman; Parrilo, Pablo A.; Vanli, Nuri Denizcan
作者单位：University of Toronto; University of Toronto; Massachusetts Institute of Technology (MIT)
摘要：Semidetinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although SDPs can be solved to arbitrary precision in polynomial time, generic convex solvers do not scale well with the dimension of the problem. In order to address this issue, Burer and Monteiro (Math Program 95(2):329-357, 2003) proposed to reduce the dimension of the problem by appealing to a low-rank factorization and solve the subs...
-
作者：Traub, Vera; Trobst, Thorben
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Irvine
摘要：We consider the capacitated cycle covering problem: given an undirected, complete graph G with metric edge lengths and demands on the vertices, we want to cover the vertices with vertex-disjoint cycles, each serving a demand of at most one. The objective is to minimize a linear combination of the total length and the number of cycles. This problem is closely related to the capacitated vehicle routing problem (CVRP) and other cycle cover problems such as min-max cycle cover and bounded cycle co...
-
作者：Ryu, Ernest K.; Hannah, Robert; Yin, Wotao
作者单位：Seoul National University (SNU); University of California System; University of California Los Angeles
摘要：Many iterative methods in applied mathematics can be thought of as fixed-point iterations, and such algorithms are usually analyzed analytically, with inequalities. In this paper, we present a geometric approach to analyzing contractive and non-expansive fixed point iterations with a new tool called the scaled relative graph. The SRG provides a correspondence between nonlinear operators and subsets of the 2D plane. Under this framework, a geometric argument in the 2D plane becomes a rigorous p...
-
作者：Cheon, Myun-Seok
作者单位：Exxon Mobil Corporation
摘要：This paper discusses an outer-approximation guided optimization method for constrained neural network inverse problems with rectified linear units. The constrained neural network inverse problems refer to an optimization problem to find the best set of input values of a given trained neural network in order to produce a predefined desired output in presence of constraints on input values. This paper analyzes the characteristics of optimal solutions of neural network inverse problems with recti...
