The strong conjecture on subpolynomial additive error in weighted grid graphs
Statement
Let be the integer grid graph with edge set , and let be an edge weighting. For vertices , write and consider the additive error . Strong conjecture. There is no weighting whose additive error is subpolynomial, namely . The paper proves a polynomial additive-stretch bound, but improving this to subpolynomial additive error would require a new approach; the conjecture remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.