Name
Title | ||
|---|---|---|
An algorithm for a separable integer programming problem with cumulatively bounded variables |
Abstract | ||
|---|---|---|
An algorithm is presented for obtaining the optimal solution of an integer programming problem in which the nested constraints represent the cumulative bounding of the variables and the objective function is a sum of concave functions of one variables. The algorithm requires O( m log( m )log 2 ( b m / m )) time, where m is the number of variables and b m is an upper bound on the sum of the m variables, b m ⩾ m ⩾1. It is also demonstrated that a special case of identical concave functions is solvable in O( m ). Both results significantly improve the previous bounds for these problems. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1016/0166-218X(87)90070-9 | Discrete Applied Mathematics |
Keywords | Field | DocType |
bounded variable,separable integer programming problem,cumulant | Discrete mathematics,Combinatorics,Upper and lower bounds,Separable space,Concave function,Algorithm,Integer programming,Mathematics,Special case,Bounding overwatch,Bounded function | Journal |
Volume | Issue | ISSN |
16 | 2 | Discrete Applied Mathematics |
Citations | PageRank | References |
2 | 0.49 | 2 |
Authors | ||
1 | ||