-
作者：Benedek, Marton; Biro, Peter; Kern, Walter; Palvoelgyi, Domotor; Paulusma, Daniel
作者单位：Corvinus University Budapest; University of Twente; Durham University
摘要：We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a fair way. A partitioned matching game (N, v) is defined on a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setle...
-
作者：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...
-
作者：Kim, Do Sang; Nguyen, Minh Tung; Pham, Tien-Son
作者单位：Pukyong National University; Ho Chi Minh University of Banking (HUB); Dalat University
摘要：In this work, the notions of normal cones at infinity to unbounded sets and limiting and singular subdifferentials at infinity for extended real value functions are introduced. Various calculus rules for these notions are established. A complete characterization of the Lipschitz continuity at infinity for lower semicontinuous functions is given. The obtained results are aimed ultimately at applications to diverse problems of optimization, such as optimality conditions, coercive properties, wea...
-
作者：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 ...
-
作者：Hertrich, Christoph; Sering, Leon
作者单位：Universite Libre de Bruxelles; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：This paper studies the expressive power of artificial neural networks with rectified linear units. In order to study them as a model of real-valued computation, we introduce the concept of Max-Affine Arithmetic Programs and show equivalence between them and neural networks concerning natural complexity measures. We then use this result to show that two fundamental combinatorial optimization problems can be solved with polynomial-size neural networks. First, we show that for any undirected grap...
-
作者：Muehlebach, Michael; Jordan, Michael I.
作者单位：Max Planck Society; University of California System; University of California Berkeley
摘要：We exploit analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems to design a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected gradients, these algorithms avoid optimization over the entire feasible set at each iteration. We prove convergence to stationary points even in a nonconvex setting and we derive accelerated rates for the convex setting both in continuous time, as well as in dis...
-
作者：Liu, Jia; Chen, Zhiping; Xu, Huifu
作者单位：Xi'an Jiaotong University; Chinese University of Hong Kong
摘要：In this paper, we consider a multistage expected utility maximization problem where the decision maker's utility function at each stage depends on historical path and the information on the true utility function is incomplete. To mitigate the adverse impact arising from ambiguity regarding the true utility, we propose a maximin robust model where the optimal policy is based on the worst-case sequence of utility functions from an ambiguity set constructed with partially available information ab...
-
作者：Nagele, Martin; Nobel, Christian; Santiago, Richard; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：There has been significant work recently on integer programs (IPs) min{c(inverted perpendicular)x: Ax <= b, x is an element of Z(n)} with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant Delta is an element of Z(>0), Delta-modular IPs are efficiently solvable, which are IPs where the constraint matrix A is an element of Z(mxn) has full column rank and all n x n minors of A are within {-Delta, . . . ,Delta}. Previous...
