### 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.