-
作者：Chekuri, Chandra; Quanrud, Kent; Torres, Manuel R.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Purdue University System; Purdue University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider approximation algorithms for packing integer programs (PIPs) of the form max[ (c, x) Ax < b, x E {0, 1r} where A, h and c are nonnegative. We let W = mini, / kJ denote the width of A which is at least 1. Previous work by Bansal et al. (Theory Comput 8(24):533-565, 2012) obtained an Q /11,,) approximation ratio A6 where A() is the maximum number of nonzeroes in any column of A (in other words the 4 -column sparsity of A). They raised the question of obtaining approximation ratios ba...
-
作者：Berndt, Sebastian; Jansen, Klaus; Klein, Kim-Manuel
作者单位：University of Kiel; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of ...
-
作者：Paat, Joseph; Weismantel, Robert; Weltge, Stefan
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Munich
摘要：A classic result of Cook et al. (Math. Program. 34:251-264, 1986) bounds the distances between optimal solutions of mixed-integer linear programs and optimal solutions of the corresponding linear relaxations. Their bound is given in terms of the number of variables and a parameter Delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt}...
-
作者：Kurpisz, Adam; Leppanen, Samuli; Mastrolilli, Monaldo
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Universita della Svizzera Italiana
摘要：We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of well-behaved univariate polynomial inequalities. We illustrate the technique on two problems, one unconstrained and the other with constraints. More precisely, we give a short elementary proof of Grigoriev/Laurent lower bound for...
-
作者：Linhares, Andre; Olver, Neil; Swamy, Chaitanya; Zenklusen, Rico
作者单位：University of Waterloo; University of London; London School Economics & Political Science; Centrum Wiskunde & Informatica (CWI); Vrije Universiteit Amsterdam; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the constraints of the other matroids. In addition to the classical steps of iterative relaxation approaches, we iterativelyrefineinvolved matroid constraints. This leads to more restrictive constraint systems whose structure can be exploited to prove the existence of constraints that c...
-
作者：Philpott, A. B.; Wahid, F.; Bonnans, J. F.
作者单位：University of Auckland; Inria
摘要：Mixed integer dynamic approximation scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description ofMIDAS, and prove its almost-sure convergence to a 2T e-optimal policy for problems with T stages when the Bellman functions are known to be monotonic, and the sampling...
-
作者：Luke, D. Russell; Teboulle, Marc; Thao, Nguyen H.
作者单位：University of Gottingen; Tel Aviv University; Delft University of Technology; Can Tho University
摘要：We present necessary conditions for monotonicity of fixed point iterations of mappings that may violate the usual nonexpansive property. Notions of linear-type monotonicity of fixed point sequences-weaker than Fejer monotonicity-are shown to imply metric subregularity. This, together with the almost averaging property recently introduced by Luke et al. (Math Oper Res, 2018. 10.1287/moor.2017.0898), guarantees linear convergence of the sequence to a fixed point. We specialize these results to t...
-
作者：Hunkenschroder, Christoph; Reuland, Gina; Schymura, Matthias
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364-1391, 2013) described a deterministic single-exponential time algorithm for the closest vector problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be c-compact if every facet normal o...
-
作者：Pohl, Mathias; Ristig, Alexander; Schachermayer, Walter; Tangpi, Ludovic
作者单位：University of Vienna; University of Vienna; Princeton University
摘要：Understanding the structure of financial markets deals with suitably determining the functional relation between financial variables. In this respect, important variables are the trading activity, defined here as the number of tradesN, the traded volumeV, the asset priceP, the squared volatility sigma 2 the bid-ask spreadSand the cost of tradingC. Different reasonings result in simple proportionality relations (scaling laws) between these variables. A basic proportionality is established betwe...
-
作者：Baiou, Mourad; Barahona, Francisco
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Clermont Auvergne (UCA); International Business Machines (IBM); IBM USA
摘要：The maximum number of edge-disjoint spanning trees in a network has been used as a measure of the strength of a network. It gives the number of disjoint ways that the network can be fully connected. This suggests a game theoretic analysis that shows the relative importance of the different links to form a strong network. We introduce the Network strength game as a cooperative game defined on a graph G=(V,E). The player set is the edge-set E and the value of a coalition S subset of Eis the maxi...
