Reducibility bounds of objective functions over the integers
Eisenbrand, Friedrich; Hunkenschroeder, Christoph; Klein, Kim-Manuel; Koutecky, Martin; Levin, Asaf; Onn, Shmuel
2023

Abstract

We study the settings where we are given a separable objective function of n variables defined in a given box of integers. We show that in many cases we can replace the given objective function by a new function with a much smaller domain. Our results apply to linear functions as well as to nonlinear separable convex objective functions.(c) 2023 Elsevier B.V. All rights reserved.

Details

Title Reducibility bounds of objective functions over the integers
Author(s) Eisenbrand, Friedrich ; Hunkenschroeder, Christoph ; Klein, Kim-Manuel ; Koutecky, Martin ; Levin, Asaf ; Onn, Shmuel
Published in Operations Research Letters
Volume 51
Issue 6
Pages 595-598
Date 2023-10-16
Publisher Elsevier, Amsterdam
ISSN 0167-6377
1872-7468
Keywords
DOI https://doi.org/10.1016/j.orl.2023.10.001
Other identifier(s) View record in Web of Science
Laboratories DISOPT
Record Appears in Scientific production and competences > SB - School of Basic Sciences > MATH - Institute of Mathematics > DISOPT - Chair of Discrete Optimization
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Grant Swiss National Science Foundation (SNSF): 163071
Deutsche Forschungsgemeinschaft (DFG): KL3408/1-1
Israel Science Foundation: 308/18
Dresner Chair at the Technion
Charles University: UNCE/SCI/004
GACR: 22-22997S
Record creation date 2024-02-19