Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871322 | Discrete Applied Mathematics | 2018 | 14 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Frédéric Meunier, Pauline Sarrabezolles,