Please use this identifier to cite or link to this item:

`https://hdl.handle.net/20.500.11851/2018`

Title: | A Fully Polynomial Time Approximation Scheme for Refutations in Weighted Difference Constraint Systems |

Authors: | Çaşkurlu, Buğra Williamson, Matthew Subramani, Kiruba Sankaran Mkrtchyan, Vahan Wojciechowski, Piotr 56295 |

Keywords: | Difference constraint systems No-certificate Approximation algorithms " Graph theory Negative cost cycle Certification |

Issue Date: | 2018 |

Publisher: | SPRINGER International Publishing AG |

Source: | Caskurlu, B., Williamson, M., Subramani, K., Mkrtchyan, V., & Wojciechowski, P. (2018, February). A Fully Polynomial Time Approximation Scheme for Refutations in Weighted Difference Constraint Systems. In Conference on Algorithms and Discrete Applied Mathematics (pp. 45-58). Springer, Cham. |

Abstract: | This paper is concerned with the design and analysis of approximation algorithms for the problem of finding the least weight refutation in a weighted difference constraint system (DCS). In a weighted DCS (WDCS), a positive weight is associated with each constraint. Every infeasible DCS has a refutation, which attests to its infeasibility. The length of a refutation is the number of constraints used in the derivation of a contradiction. Associated with a DCS D is its constraint network G. D is infeasible if and only if G has a simple, negative cost cycle. It follows that the shortest refutation of D corresponds to the length of the shortest negative cost cycle in G. The constraint network of a WDCS is represented by a constraint network, where each edge contains both a cost and a positive, integral length. In the case of a WDCS, the weight of a refutation is defined as the sum of the lengths of the edges corresponding to the refutation. The problem of finding the minimum weight refutation in a WDCS is called the weighted optimal length resolution refutation (WOLRR) problem and is known to be NP-hard. In this paper, we describe a pseudo-polynomial time algorithm for the WOLRR problem and convert it into a fully polynomial time approximation scheme (FPTAS). We also generalize our FPTAS to determine the optimal length refutation of a class of constraints called Unit Two Variable per Inequality (UTVPI) constraints. |

Description: | 4th International Conference on Algorithms and Discrete Applied Mathematics (2018 : Guwahati; India) |

URI: | https://link.springer.com/chapter/10.1007%2F978-3-319-74180-2_4 https://hdl.handle.net/20.500.11851/2018 |

ISBN: | 978-3-319-74180-2 978-3-319-74179-6 |

ISSN: | 0302-9743 |

Appears in Collections: | Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection |

Show full item record

CORE Recommender

Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.