2013/02/14 by Stephen G. Hartke, Hartke, Stephen G., Derrick Stolee +1 · 1 citation
Computer Science · Mathematics · #05D05 #68R05 #90C27 #Algebraic Geometry and Number Theory #Analytic Number Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Meromorphic and Entire Functions #cs.DM #math.CO #msc:05D05 #msc:68R05 #msc:90C27
paper · pdf · doi:10.48550/arxiv.1302.3636
23 pages, 1 figure, 4 tables
arxiv created 2013/02/14 · openalex publication_date 2013/02/14 · arxiv updated 2013/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.