Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/767
Title: On approximating optimal weight “no”-certificates in weighted difference constraint systems
Authors: Çaşkurlu, Buğra
Williamson, Matthew
Subramani, Kiruba Sankaran
Mkrtchyan, Vahan
56295
Keywords: Difference constraint system
“No”-certificate
Approximation algorithm
Graph theory
Negative cost cycle
Certification
Issue Date: 1-Jul-2018
Publisher: Springer New York LLC
Source: Caskurlu, B., Williamson, M., Subramani, K., & Mkrtchyan, V. (2018). On approximating optimal weight “no”-certificates in weighted difference constraint systems. Journal of Combinatorial Optimization, 36(2), 329-345.
Abstract: This paper is concerned with the design and analysis of approximation algorithms for the problem of determining the least weight refutation in a weighted difference constraint system. Recall that a difference constraint is a linear constraint of the form xi- xj≤ bij and a conjunction of such constraints is called a difference constraint system (DCS). In a weighted DCS (WDCS), a positive weight is associated with each constraint. Every infeasible constraint system has a refutation, which attests to its infeasibility. In the case of a DCS, this refutation is a subset of the input constraints, which when added together produces a contradiction of the form 0 ≤ - b, b> 0. It follows that every refutation acts as a “no”-certificate. The length of a refutation is the number of constraints used in the derivation of a contradiction. Associated with a DCS D: A· x≤ b is its constraint network G= ⟨ V, E, b⟩. It is well-known that D is infeasible if and only if G contains a simple, negative cost cycle. Previous research has established that every negative cost cycle of length k in G corresponds exactly to a refutation of D using k constraints. It follows that the shortest refutation of D (i.e., the refutation which uses the fewest number of constraints) corresponds to the length of the shortest negative cycle in G. The constraint network of a WDCS is represented by a constraint network G= ⟨ V, E, b, l⟩ , where l: E→ N represents a function which associates a positive, integral length with each edge in G. 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). © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
URI: https://link.springer.com/article/10.1007%2Fs10878-018-0292-8
https://hdl.handle.net/20.500.11851/767
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)

80
checked on Feb 6, 2023

Google ScholarTM

Check

Altmetric


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