39 problems
Let be a finite set of finite strings. For strings and , let be the maximum length of a string that is simultaneously a suffix of and a pref…
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…
For every fixed finite graph and every , there is a deterministic quasipolynomial-time algorithm that, given a graph with nonnegative vertex weights and cont…
Given a finite point set with , let range over spanning trees on , with each edge weighted by its Euclidean length. Define the dilation of …
This entry tracks Gutin–Yeo weighted Max-Cut conjecture. It settles a natural threshold on a substantial subclass while improving the best general bound. Latest development The pap…
For every connected graph , the broadcast domination number is at most twice the multipacking number: , where is the minimum…
Approximation conjecture. There is a function such that for every integer , there is a polynomial-time algorithm which, given a tournament , correctly concludes that…
Let be a doubly stochastic matrix, so that its entries are non-negative and every row and column sums to . The permanent is denoted by…
The optimality conjecture. The particular polynomial is optimal in the sense that
Bounded-size inversion approximation hardness conjecture. There exists such that, unless , for every and every , no polynomial-time…
Morell–Skutella-type conjecture. Given a -transshipment , one can efficiently compute an unsplittable -transshipment such that
Bertsimas–Grigni conjecture. For every linear order on the unit square,
Abelian embedding conjecture. For a distribution on , Conclusion $$ holds if and only if admits no Abelian embedding.
Let consist of independent random points uniformly distributed in , and let a bipartite coloring of be any coloring induced by a Euclidean minimum spanning…
Let be a finite point set. A bipartite coloring is obtained by choosing a Euclidean minimum spanning tree of and partitioning so that every…
Priestley's conjecture. -ECSM admits a polynomial-time -approximation algorithm.
Let be the number of subsets, let be the inclusion probability, and let be the number of elements. Write for the value produced by th…
Let be the number of subsets, let be the inclusion probability, and let be the number of elements. Write for the value produced by th…
Let be the number of subsets, let be the inclusion probability, and let be the number of elements. Write for the value produced by th…
Approximation-hardness conjecture. Unless P=NP, there is no -approximation algorithm for computing or .
Pseudodistribution product inequality.
Let sparse graphs have edges, and consider the four variants obtained by choosing directed or undirected graphs and weighted or unweighted edges. For…
A cubic graph is a graph in which every vertex has degree three. Mohar's conjecture. Approximating the genus of cubic graphs is APX-hard. This conjecture asserts computational hard…
Let be a hypergraph, let be edge weights, and let be a fractional matching, meaning that … where …