2026/08/04 by Patrick Bennett, Alan Frieze, Wesley Pegden
Mathematics · Computer Science · #math.CO #cs.DS
arxiv created 2026/08/04 · arxiv updated 2026/08/05
We present an average case model of classical problems in combinatorial optimization where there are color constraints. In all cases we seek some (spanning) sub-structure of a complete graph of minimum cost. The edges are randomly colored either red or blue. We bias against the red edges by placing a bound on the number of them that are allowed in our structure. This bound will be lower w.h.p. than what would occur without discrimination. We examine the effect of this bias on the minimum cost of a desired structure. We consider minimum cost spanning trees, shortest paths, minimum cost perfect matchings and the asymmetric traveling salesperson problem.