A simple but NP-hard problem of mixed-discrete programming and its solution by approximate algorithms

Abstract

A NP-hard problem (P) of mixed-discrete linear programming is considered which consists in the minimization of a linear objective function subject to a special non-connected subset of an unbounded polymatroid. For this problem we describe three polynomial approximate algorithms including a greedy algorithm and a fully polynomial approximation scheme solving a special subproblem of (P).

Keywords:

• Mixed-discrete programming
• polynomial algorithms
• approximate algorithms
• greedy algorithm
• fully polynomial approximation scheme

AMS 1980 Subject Classifications:

• Primary: 90 C 11