Abstract: Various combinatorial problems are effectively modelled in terms of (0,1) matrices. Origins are coming from n-cube geometry, hypergraph theory, inverse tomography problems, or directly from different models of application problems. Basically these problems are NP-complete. The paper considers a set of such problems and introduces approximation algorithms for their solutions applying Lagragean relaxation and related set of techniques.

Keywords: Approximation algorithms, Lagragean relaxation

ACM Classification Keywords: G.2.1 Discrete mathematics: Combinatorics

Link:

LAGRANGEAN APPROXIMATION FOR COMBINATORIAL INVERSE PROBLEMS

Hasmik Sahakyan, Levon Aslanyan

http://www.foibg.com/ibs_isc/ibs-01/IBS-01-p02.pdf