Please use this identifier to cite or link to this item:
Fulltext available Open Access
arXiv ID: 1909.07326
Title: Multitype integer monoid optimization and applications
Language: English
Authors: Knop, Dušan 
Koutecký, Martin 
Levin, Asaf 
Mnich, Matthias  
Onn, Shmuel 
Keywords: integer programming; configuration IP; proximity theorems; scheduling
Issue Date: 16-Sep-2019
Source: arXiv:1909.07326 (2019)
Abstract (english): 
Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems since the pioneering work of Gilmore and Gomory [Oper. Res., 1961].
Configuration IPs have one variable for each possible configuration, which describes a placement of items into a location, and whose value corresponds to the number of locations with that placement. In high multiplicity problems items come in types, and are represented succinctly by a vector of multiplicities; solving the configuration IP then amounts to deciding whether the input vector of multiplicities of items of each type can be decomposed into a given number of configurations.
We make this typically implicit notion explicit by observing that the set of all input vectors which can be decomposed into configurations forms a monoid of configurations, and the problem corresponding to solving the configuration IP is the Monoid Decomposition problem. Then, motivated by applications, we enrich this problem in two ways. First, in certain problems each configuration additionally has an objective value, and the problem becomes an optimization problem of finding a “best” decomposition under the given objective. Second, there are often different types of configurations derived from different types of locations. The resulting problem is then to optimize over decompositions of the input multiplicity vector into configurations of several types, and we call it Multitype Integer Monoid Optimization, or simply MIMO.
We develop fast exact (exponential-time) algorithms for various MIMO with few or many location types and with various objectives. Our algorithms build on a novel proximity theorem which connects the solutions of a certain configuration IP to those of its continuous relaxation.
We then cast several fundamental scheduling and bin packing problems as MIMOs, and thereby obtain new or substantially faster algorithms for them.
We complement our positive algorithmic results by hardness results which show that, under common complexity assumptions, the algorithms cannot be extended into more relaxed regimes.
DOI: 10.15480/882.4138
Institute: Algorithmen und Komplexität E-11 
Document Type: Preprint
Project: Multivariate Algorithmen für Scheduling mit hoher Multiplizität 
More Funding information: Deutsche Forschungsgemeinschaft (DFG), OP VVV MEYS Research Center for Informatics, Israel Science Foundation, Charles University, GA ČR, German-Israeli Foundation for Scientific Research and Development (GIF), Dresner Chair, MaMu, NI 369/19, CZ.02.1.01/0.0/0.0/16 019/0000765, 308/18, UNCE/SCI/004, 7-0914-2S, I-1366- 407.6/2016, MN 59/4-1
License: In Copyright In Copyright
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
1909.07326.pdf819,88 kBAdobe PDFView/Open
Show full item record

Page view(s)

Last Week
Last month
checked on Jun 2, 2023


checked on Jun 2, 2023

Google ScholarTM


Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.