-
作者：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...
-
作者：Luke, D. Russell; Schultze, Steffen; Grubmuller, Helmut
作者单位：University of Gottingen
摘要：We apply a recently developed framework for analyzing the convergence of stochastic algorithms to the general problem of large-scale nonconvex composite optimization more generally, and nonconvex likelihood maximization in particular. Our theory is demonstrated on a stochastic gradient descent algorithm for determining the electron density of a molecule from random samples of its scattering amplitude. Numerical results on an idealized synthetic example provide a proof of concept. The algorithm...
-
作者：Weninger, Noah; Fukasawa, Ricardo
作者单位：University of Waterloo
摘要：In the minimum spanning tree (MST) interdiction problem, we are given a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document} with edge weights, and want to find some X subset of E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage...
-
作者：Huang, Kun; Pu, Shi; Nedic, Angelia
作者单位：The Chinese University of Hong Kong, Shenzhen; Arizona State University-Tempe; Arizona State University; Arizona State University-Tempe
-
作者：Liang, Wei; Tang, Shaojie; Zhang, Zhao
作者单位：Zhejiang Normal University
摘要：In this paper, we introduce a polynomial-time 2-approximation algorithm for the Unrooted Prize-Collecting Forest with K Components (URPCFK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {URPCF}_K$$\end{document}) problem. Given a graph G and an integer K, URPCFK\documentclass[12pt]{minimal} \usepackage{amsmat...
-
作者：Andreani, Roberto; Haeser, Gabriel; Mito, Leonardo M.; Ramirez, Hector
作者单位：Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidad de Chile; Universidad de Chile
摘要：In a previous paper [Andreani et al, Math. Prog. 202, p. 473-514, 2023] we introduced a constant rank constraint qualification for nonlinear semidefinite and second-order cone programming by considering all faces of the underlying cone. This condition is independent of Robinson's condition and it implies a strong second-order necessary optimality condition which depends on a single Lagrange multiplier instead of the full set of Lagrange multipliers. In this paper we expand on this result in se...
-
作者：Bhathena, Aaresh; Fattahi, Salar; Gomez, Andres; Kucukyavuz, Simge
作者单位：University of Michigan System; University of Michigan; University of Southern California; Northwestern University
摘要：This paper investigates convex quadratic optimization problems involving n indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix Q defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this problem in time and memory complexity of O(n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepa...
-
作者：Curtis, Frank E.; Jiang, Xin; Wang, Qi
作者单位：Lehigh University
摘要：An interior-point algorithm framework is proposed, analyzed, and tested for solving nonlinearly constrained continuous optimization problems. The main setting of interest is when the objective and inequality constraint functions may be nonlinear and/or nonconvex, and when constraint values and derivatives are tractable to compute, but objective function values and derivatives can only be estimated. The algorithm is intended primarily for a setting that is similar for stochastic-gradient method...
-
作者：Chen, Liang; Chen, Ruoning; Sun, Defeng; Zhang, Liping
作者单位：Hunan University; Tsinghua University; Hong Kong Polytechnic University
摘要：In this paper, we study the Aubin property of the Karush-Kuhn-Tucker solution mapping for the nonlinear semidefinite programming (NLSDP) problem at a locally optimal solution. In the literature, it is known that the Aubin property implies the constraint nondegeneracy by Fusek (SIAM J. Optim. 23:1041-1061, 2013) and the second-order sufficient condition by Ding et al. (SIAM J. Optim. 27:67-90, 2017). Based on the Mordukhovich criterion, here we further prove that the strong second-order suffici...
-
作者：Hunkenschroder, Christoph; Klein, Kim-Manuel; Koutecky, Martin; Lassota, Alexandra; Levin, Asaf
作者单位：Technical University of Berlin; University of Lubeck; Charles University Prague; Eindhoven University of Technology; Technion Israel Institute of Technology
摘要：We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs have a constraint matrix with independent blocks linked together by few constraints in a recursive pattern. Transposing this constraint matrix yields the constraint matrix of multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to ask whether this gap is inherent. We answer this question in the affirmative. A...
