-
作者：Au, Yu Hin; Tuncel, Levent
作者单位：University of Saskatchewan; University of Waterloo
摘要：We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov & aacute;sz-Schrijver SDP operator LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document}, with a particular focus on finding and characterizing the smallest graphs with a given LS+\doc...
-
作者：Luke, D. Russell
作者单位：University of Gottingen
摘要：We present a Markov-chain analysis of blockwise-stochastic algorithms for solving partially block-separable optimization problems. Our main contributions to the extensive literature on these methods are statements about the Markov operators and distributions behind the iterates of stochastic algorithms, and in particular the regularity of Markov operators and rates of convergence of the distributions of the corresponding Markov chains. This provides a detailed characterization of the moments o...
-
作者：Au, Yu Hin; Tuncel, Levent
作者单位：University of Saskatchewan; University of Waterloo
摘要：We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov & aacute;sz-Schrijver SDP operator LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document}. In particular, we focus on a search for relatively small graphs with high LS+\documentclass[12...
-
作者：Del Pia, Alberto
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：In this paper we consider the problem of minimizing a general quadratic function over the mixed integer points in an ellipsoid. This problem is strongly NP-hard, NP-hard to approximate within a constant factor, and optimal solutions can be irrational. In our main result we show that an arbitrarily good solution can be found in polynomial time, if we fix the number of integer variables. This algorithm provides a natural extension to the mixed integer setting, of the polynomial solvability of th...
-
作者：Jiang, Nan; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This paper studies distributionally robust chance constrained programs (DRCCPs), where the uncertain constraints must be satisfied with at least a probability of a prespecified threshold for all probability distributions from the Wasserstein ambiguity set. As DRCCPs are often nonconvex and some DRCCPs may not have mixed-integer reformulations, researchers have been developing various convex inner approximations. Recently, ALSO-X has been proven to outperform the conditional value-at-risk (CVaR...
-
作者：Kobayashi, Yusuke
作者单位：Kyoto University
摘要：In the optimal general factor problem, 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} and a set B(v)subset of Z\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \...
-
作者：Santiago, Richard; Sergeev, Ivan; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an O(1)-competitive algorithm for the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid appear one-by-one, revealing their weight at appearance, and the task is to select elements online with the goal to get an independent set of largest possible weight. O(1)-competitive MSP algorithms have so far only been obtained for restricted matroid classes and for MSP v...
-
作者：Aragon-Artacho, Francisco J.; Mordukhovich, Boris S.; Perez-Aros, Pedro
作者单位：Universitat d'Alacant; Wayne State University; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：This paper addresses the study of a new class of nonsmooth optimization problems, where the objective is represented as a difference of two generally nonconvex functions. We propose and develop a novel Newton-type algorithm to solving such problems, which is based on the coderivative generated second-order subdifferential (generalized Hessian) and employs advanced tools of variational analysis. Well-posedness properties of the proposed algorithm are derived under fairly general requirements, w...
-
作者：Jaeger, Sven; Sagnol, Guillaume; Waldschmidt, Daniel Schmidt genannt; Warode, Philipp
作者单位：Technical University of Berlin; Humboldt University of Berlin
摘要：We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of 3 for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any b > 1 a tight analysis for the natural b-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of(1+3 root 3) approxi...
-
作者：Wang, Alex L.; Jiang, Rujun
作者单位：Carnegie Mellon University; Purdue University System; Purdue University; Fudan University
摘要：A set of quadratic forms is simultaneously diagonalizable via congruence (SDC) if there exists a basis under which each of the quadratic forms is diagonal. This property appears naturally when analyzing quadratically constrained quadratic programs (QCQPs) and has important implications in globally solving such problems using branch-and-bound methods. This paper extends the reach of the SDC property by studying two new weaker notions of simultaneous diagonalizability. Specifically, we say that ...
