In this note the k-sum linear programming problem (KLP) is introduced, which subsumes the classical linear programming problem and the minmax linear programming problem. KLP can be transformed into a linear program with an exponential number of additional constraints and one additional variable. Exploiting the special structure of these additional constraints, it is shown that KLP can be solved in polynomial time. Two promising simplex-based algorithms are also suggested to solve KLP.
