-
作者：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....
-
作者：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...
-
作者：Mai, Ngoc Hoang Anh; Lasserre, Jean-Bernard; Magron, Victor
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：In a first contribution, we revisit two certificates of positivity on (possibly non-compact) basic semialgebraic sets due to Putinar and Vasilescu (C R Acad Sci Ser I Math 328(6):495-499, 1999). We use Jacobi's technique from (Math Z 237(2):259-273, 2001) to provide an alternative proof with an effective degree bound on the sums of squares weights in such certificates. As a consequence, it allows one to define a hierarchy of semidefinite relaxations for a general polynomial optimization proble...
-
作者：Naderi, Mohammad Javad; Buchanan, Austin; Walteros, Jose L.
作者单位：Oklahoma State University System; Oklahoma State University - Stillwater; State University of New York (SUNY) System; University at Buffalo, SUNY
摘要：The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) for the clique problem that have more desirable worst-case properties, especially for sparse graphs. The smallest MIP that we pro...
-
作者：Kiraly, Csaba; Mihalyko, Andras
作者单位：Eotvos Lorand University; HUN-REN
摘要：For two integers k > 0 and l, a graph G = (V, E) is called (k, l)-tight if vertical bar E vertical bar = k vertical bar V vertical bar-l and i(G)(X) <= k vertical bar X vertical bar-l for each X subset of V for which i(G)(X) >= 1, where i(G)(X) denotes the number of induced edges by X. G is called (k, l)-redundant if G - e has a spanning (k, l)-tight subgraph for all e is an element of E. We consider the following augmentation problem. Given a graph G = (V, E) that has a (k, l)-tight spanning ...
