Please use this identifier to cite or link to this item:
|Title:||A Fully Polynomial Time Approximation Scheme for Refutations in Weighted Difference Constraint Systems||Authors:||Çaşkurlu, Buğra
Subramani, Kiruba Sankaran
|Keywords:||Difference constraint systems
Approximation algorithms "
Negative cost cycle
|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
|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
checked on Dec 26, 2022
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.