-
作者：Marinkovic, Javier; Soto, Jose A.; Verdugo, Victor
作者单位：Universidad de Chile; Universidad de Chile; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile; University System of Maryland; University of Maryland College Park
摘要：We consider an online multi-weighted generalization of several classic online optimization problems called the online combinatorial assignment problem. We are given an independence system over a ground set of elements and agents that arrive online one by one. Upon arrival, each agent reveals a weight function over the elements of the ground set. If the independence system is given by the matchings of a hypergraph, we recover the combinatorial auction problem, where every node represents an ite...
-
作者：Del Pia, Alberto; Kaibel, Volker
作者单位：University of Wisconsin System; University of Wisconsin Madison
-
作者：Lu, Zhaosong; Mei, Sanyou
作者单位：University of Minnesota System; University of Minnesota Twin Cities
摘要：In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method developed in this paper. Under some suitable assumptions, an operation complexity of O(epsilon-4log epsilon-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} ...
-
作者：Hoppenot, Pierre; Martin, Mathis; Szigeti, Zoltan
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：The seminal papers of Edmonds (Combinatorial algorithms, Academic Press, New York, 1973), Nash-Williams (J Lond Math Soc 36:445-450, 1961) and Tutte (J Lond Math Soc 36:221-230, 1961) have laid the foundations of the theories of packing arborescences and packing trees. The directed version has been extensively investigated, resulting in a great number of generalizations. In contrast, the undirected version has been marginally considered. The aim of this paper is to further develop the theories...
-
作者：Lu, Haihao; Yang, Jinwen
作者单位：Massachusetts Institute of Technology (MIT); University of Chicago
摘要：We study the convergence behaviors of primal-dual hybrid gradient (PDHG) for solving linear programming (LP). PDHG is the base algorithm of a new general-purpose first-order method LP solver, PDLP, which aims to scale up LP by taking advantage of modern computing architectures. Despite its numerical success, the theoretical understanding of PDHG for LP is still very limited; the previous complexity result relies on the global Hoffman constant of the KKT system, which is known to be very loose ...
-
作者：Garber, Dan; Kaplan, Atara
作者单位：Technion Israel Institute of Technology
摘要：Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in developing efficient methods for smooth problems that avoid computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced.In this paper we consider a standard convex relaxation: minimizing a convex nonsmooth objective function over the spectrahedron (set of real positive-semidefinite matrices with unit trac...
-
作者：Gutekunst, Samuel C.; Jin, Billy; Williamson, David P.
作者单位：Bucknell University; Cornell University; Purdue University System; Purdue University
摘要：The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of the input, remarkably little is known about the symmetric circulant TSP, and the complexity of the problem has been an often-cited open question. Considerable effort has been made to understand the case in which only edges of two lengths are allowed to have finite cost: the two-stripe symmetric circulant TSP. In this ...
-
作者：Belotti, Pietro
作者单位：Polytechnic University of Milan
摘要：We consider an n-variate monomial function that is restricted both in value by lower and upper bounds and in domain by two homogeneous linear inequalities. Monomial functions are building blocks for the class of Mixed Integer Nonlinear Optimization problems, which has many practical applications. We show that the upper envelope of the function in the given domain, for n >= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepa...
-
作者：Hu, Jian; Zhang, Dali; Xu, Huifu; Zhang, Sainan
作者单位：University of Michigan System; University of Michigan Dearborn; Shanghai Jiao Tong University; Chinese University of Hong Kong
摘要：Utility preference robust optimization (PRO) has recently been proposed to deal with optimal decision-making problems where the decision maker's (DM's) preference over gains and losses is ambiguous. In this paper, we take a step further to investigate the case that the DM's preference is random. We propose to use a random utility function to describe the DM's preference and develop distributional utility preference robust optimization (DUPRO) models when the distribution of the random utility ...
-
作者：Sudakov, Benny; Tomon, Istvan
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Umea University
摘要：Given an mxn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\times n$$\end{document} binary matrix M with |M|=pmn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargi...
