Reducibility bounds of objective functions over the integers

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.

Keywords

• Integer programming
• Analysis of algorithms
• Separable convex objective