Bridging between 0/1 and linear programming via random walks

DOI10.1145/3313276.3316347zbMath1433.68156arXiv1904.04860OpenAlexW2963129052MaRDI QIDQ5212799

Joshua Brakensiek, Venkatesan Guruswami

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.04860

zbMATH Keywords

linear programminginteger programmingrandom walksconstraint satisfaction problemsstrong exponential time hypothesis

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Stochastic programming (90C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Computational aspects of satisfiability (68R07)

Related Items

Unnamed Item, UP-DPC: ultra-scalable parallel density peak clustering, CNF satisfiability in a subspace and related problems, On Super Strong ETH