A fully polynomial time approximation scheme for refutations in weighted difference constraint systems

DOI10.1007/978-3-319-74180-2_4zbMath1497.68570MaRDI QIDQ2636553

Matthew Williamson, Bugra Caskurlu, Piotr J. Wojciechowski, K. Subramani and Vahan Mkrtchyan, Vahan V. Mkrtchyan

Publication date: 5 June 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-74180-2_4

zbMATH Keywords

graph theory; approximation algorithms; negative cost cycle; certification; difference constraint systems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms