On approximating optimal weight ``no-certificates in weighted difference constraint systems

DOI10.1007/s10878-018-0292-8zbMath1402.90137OpenAlexW2800048262MaRDI QIDQ721917

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

Publication date: 20 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-0292-8

zbMATH Keywords

approximation algorithmgraph theorynegative cost cyclecertificationdifference constraint system``no-certificate

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal length resolution refutations of difference constraint systems
• Empirical analysis of algorithms for the shortest negative cost cycle problem
• Randomized algorithms for finding the shortest negative cost cycle in networks
• Improved algorithms for optimal length resolution refutation in difference constraint systems
• A new approach to dynamic all pairs shortest paths

This page was built for publication: On approximating optimal weight ``no-certificates in weighted difference constraint systems