A Single-Variable Method for Solving the Min–Max Programming Problem with Addition–Overlap Function Composition

Abstract

Min–max programming problems with addition–min constraints have been studied in the literature to model data transfer in BitTorrent-like peer-to-peer file-sharing systems. It is well known that the class of overlap functions contains various operators, including the “min” operator. The aim of this paper is to generalize the above min–max programming problem with addition–overlap function constraints. We demonstrate that this new optimization problem can be transformed into a simplified single-variable optimization problem, which makes it easier to find an optimal solution. The bisection method will be used to find this optimal solution. In addition, when the overlap function is explicitly specified, an iterative method is given to compute the optimal objective value with a polynomial time complexity. A numerical example is provided to illustrate the procedures.

Keywords

• min–max programming problem
• single-variable method
• addition–overlap function composition