A simple but NP-hard Problem of Mixed-discrete Programming and its Solution by Approximate Algorithms

作     者：Dempe, S. 

作者机构：Technische Hochschule Karl-Marx-Stadt Sektion Mathematik DDR - 9010 PSF 964 Karl-Marx-Stadt Germany 

出 版 物：《Optimization》 (Optimization)

年 卷 期：1985年第16卷第5期

页      面：705-714页

学科分类：0820[工学-石油与天然气工程] 12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 0811[工学-控制科学与工程] 

主　　题：Approximate algorithms Fully polynomial approximation scheme Greedy algorithm Mixed-discrete programming Polynomial algorithms 

摘      要：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 nonconnected 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). © 1985, Taylor & Francis Group, LLC. All rights reserved.