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

Page view(s)

26
checked on Dec 26, 2022

Google ScholarTM

Check

Altmetric


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