Article ID Journal Published Year Pages File Type
6871322 Discrete Applied Mathematics 2018 14 Pages PDF
Abstract
The traditional applications of colorful linear programming lie in discrete geometry. In this paper, we study its relations with other areas, such as game theory, operations research, and combinatorics. Regarding game theory, we prove that computing a Nash equilibrium in a bimatrix game is a colorful linear programming problem. We also formulate an optimization problem for colorful linear programming and show that as for usual linear programming, deciding and optimizing are computationally equivalent. We discuss then a colorful version of Dantzig's diet problem. We also propose a variant of the Bárány algorithm, which is an algorithm computing a set T whose existence is ensured by the colorful Carathéodory theorem. Our algorithm makes a clear connection with the simplex algorithm and we discuss its computational efficiency. Related complexity and combinatorial results are also provided.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,