Augmenting DAG algorithm to LP relaxation of WCSP

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F08%3A03153077" target="_blank" >RIV/68407700:21230/08:03153077 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Augmenting DAG algorithm to LP relaxation of WCSP

Original language description

Implementation of the Augmenting DAG algorithm (originally proposed by Koval and Schlesinger in 1976) to compute linear programming relaxation of the Weighted Constraint Satisfaction Problem (WCSP) (also known as maximizing Gibbs energy, or MAP inferencein Markov random fields / undirected graphical models). WCSP has many applications, e.g. in computer vision or bioinformatics. The algorithm and its efficient implementation is highly non-trivial.

Czech name

Algoritmus pro vypocet LP relaxace WCSP

Czech description

Implementace "Augmenting DAG" algoritmu (poprve navrzenem autory Koval a Schlesinger v roce 1976) pro vypocet LP relaxace problemu WCSP (weighted constraint satisfaction), WCSP je znamy take jako minimalizace Gibbsovy energie nebo MAP inference v Markovskych nahodnych polich ci neorientovanych grafovych modelech. WCSP ma mnoho aplikaci, napr. v pocitacovem videni ci bioinformatice. Algoritmus a jeho efektivni implementace jsou velmi netrivialni.

Type

R - Software

CEP classification

JD - Use of computers, robotics and its application

OECD FORD branch

—

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2008

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Internal product ID

AugDAG

Technical parameters

public domain software

Economical parameters

—

Owner IČO

68407700

Owner name

ČVUT FEL, Katedra kybernetiky