Colourful Linear Programming and its Relatives

We consider the following Colourful generalization of Linear Programming: given sets of points S₁, …, S_k ⊂ ℝ^d, referred to as colours, and a point b ∈ ℝ^d, decide whether there is a colourfulT = {s₁, …, 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₁ = ⋯ = 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₁, w₂)-Matroid-Basis-Nonbasis problems, and give an application of Colourful Linear Programming to the algorithmic problems of Tverberg's theorem in combinatorial geometry.