A Branch-and-Cut Strategy for the Manickam-Miklos-Singhi Conjecture
From MaRDI portal
Publication:6239647
DOI10.1016/J.EJC.2013.06.047arXiv1302.3636WikidataQ123080381 ScholiaQ123080381MaRDI QIDQ6239647FDOQ6239647
Authors: Stephen G. Hartke, Derrick Stolee 
Publication date: 14 February 2013
Abstract: The Manickam-Miklos-Singhi Conjecture states that when n is at least 4k, every multiset of n real numbers with nonnegative total sum has at least (n-1 choose k-1) k-subsets with nonnegative sum. We develop a branch-and-cut strategy using a linear programming formulation to show that verifying the conjecture for fixed values of k is a finite problem. To improve our search, we develop a zero-error randomized propagation algorithm. Using implementations of these algorithms, we verify a stronger form of the conjecture for all k at most seven.
Permutations, words, matrices (05A05) Linear programming (90C05) Randomized algorithms (68W20) Other combinatorial number theory (11B75) Extremal set theory (05D05)
This page was built for publication: A Branch-and-Cut Strategy for the Manickam-Miklos-Singhi Conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239647)
