Colourful Linear Programming and its Relatives

Abstract

We consider the following Colourful generalization of Linear Programming: given sets of points S 1 , …, S k ⊂ ℝ d , referred to as colours, and a point b ∈ ℝ d , decide whether there is a colourful T = {s 1 , …, s k } such that b ∈ conv(T), and if there is one, find it. Linear Programming is obtained by taking k = d + 1 and S 1 = ⋯ = S d+1 . If k = d + 1 and b ∈ ∩ i=1 d+1 conv(S i ) then a solution always exists: we describe an efficient iterative approximation algorithm for this problem, that finds a colourful T whose convex hull contains a point ϵ-close to b, and analyze its real arithmetic and Turing time complexities. In contrast, we show that Colourful Linear Programming is strongly 𝒩𝒫-complete. We consider a class of linear algebraic relatives of Colourful Linear Programming, and give a computational complexity classification of the related decision and counting problems that arise. We also introduce and discuss the complexity of a hierarchy of (w 1 , w 2 )-Matroid-Basis-Nonbasis problems, and give an application of Colourful Linear Programming to the algorithmic problems of Tverberg's theorem in combinatorial geometry.