62 problems
Submodular separation conjecture. For every such , there exists a submodular function such that is computable in time, for ever…
Conjecture. There exist an absolute constant and an online algorithm such that, for every finite matroid and every choice of nonnegative weights, the algorithm selects…
Lavi's conjecture: Let , write with integers and , and let be either row-stochastic, meaning…
For every bipartite multigraph with edge weights , let be the minimum number of colors in an edge-coloring such that, for every vertex …
Let be a matroid on ground set , let be an abelian group, let be a labeling, let be finite, and let be arbitrary costs. F…
For and a matroid of rank , let be monotone and -weakly submodular, meaning that for all disjoint…
Consider online allocation with agents having monotone submodular valuation functions . Items arrive sequentially, and each item must be irrev…
There exists a constant and infinitely many Traveling Salesman Problem instances with cities, together with an initial Hamiltonian cycle , such that every sequence o…
Let be an ideal clutter with incidence matrix , meaning that the set-covering polyhedron is integral. For every in…
Given two centered planar -point sets represented by complex numbers with , define the permutat…
For every matroid and every nonnegative weight function , when the elements of arrive in a uniformly random order and their weight…
Given a sequence of insertions of elements into a ground set, a monotone submodular function accessible through value queries, and a cardinality bound , does there exist a r…
The conjecture asserts that there exists a polynomial such that, for every and every lattice polytope , its monotone diameter…
Given a finite simple unweighted graph , decide whether the standard Goemans–Williamson semidefinite relaxation of Max-Cut has the same optimal value as the integer Max-Cu…
Let be the length of an optimal Golomb ruler with marks. Singer-type upper-bound conjecture. For every integer , … The source derives this as a consequence of th…
Reciprocal-integer deficiency conjecture. There exists an such that
Recursive upper-bound conjecture. In a -dimensional setting,
Feasible indexing conjecture. There exists an indexing satisfying this successor-set ordering and, whenever two consecutive nodes have equal successor-set order,
Weaker dijoin decomposition conjecture. The arc set can be decomposed into a -dijoin and a -dijoin, for every .
Let be a -matrix whose columns each contain the same number of 's, with column vectors . Let be the clutter associated with…
Finite exact-density tile-family conjecture. For every fixed , there is a finite coordinate-symmetric family of induced templates of independence density such that, in eve…
Let be the collection of graphs whose vertices are labeled by -subsets of an -element set, with the property that for vertices labeled by and , th…
Let , and let denote the optimal balanced discrepancy for the module-lattice sign-selection problem. Write for the constant value proposed by the…
MF-AOA asymptotic performance conjecture. In the limit , AMP algorithms such as the MF-AOA achieve a performance of approximately
Bollobás–Meir conjecture. For any finite set of points , there exists a Hamiltonian cycle on with if , and…