RelView Examples - Approximation Algorithms

```{************************************************************
Computation of a sequence of vectors approximating a mini-
mum colouring of a simple graph. The approximation algo-
rithm can be found in Emden-Weinert et al., p. 130
************************************************************}

ColourApprox(R)
DECL C, p, c
BEG  p = point(Ln1(R));
C = p * p^;
WHILE -universal(dom(C)) DO
p = point(-dom(C));
c = point(-(C^ * R * p));
C = C | p * c^
OD
RETURN C * inj(ran(C))^
END.

{************************************************************
Approximation algorithm for a minimum vertex cover of an
undirected and loop-free graph following the book of Cor-
men, Leiserson and Rivest, p. 967. The algorithm has ra-
tio bound 2
************************************************************}

VertexCovApprox(R)
DECL E, c, e
BEG  c = On1(R);
E = R;
WHILE -empty(E) DO
e = edge(E);
c = c | dom(e);
E = E & -(e*L(e) & R) & -(L(e)*e & R)
OD
RETURN c
END.

{************************************************************
Approximation algorithm for a minimum edge cover of a con-
nected undirected and loopfree graph following the book of
Cormen, Leiserson and Rivest, p. 975. There, the algorithm
is formulated for the set covering problem. The algorithm
has a ratio bound 3/2
************************************************************}

EdgeCovApprox(R)
DECL C, K, u, e
BEG  u = Ln1(R);
C = O(R);
WHILE -empty(u) DO
K = u * u^ & R;
IF -empty(K) THEN e = edge(K)
ELSE K = (u*L(u)^ | L(u)*u^) & R;
e = edge(K) FI;
u = u & -dom(e);
C = C | e
OD
RETURN C
END.

{************************************************************
Approximation algorithm for a maximum cut of an undirect-
ed and loopfree graph with ratio bound 2
************************************************************}

MaxCut(R)
DECL c1, c2, v, p
BEG  v = Ln1(R);
c1 = On1(R);
c2 = On1(R);
WHILE -empty(v) DO
p = point(v);
IF cardlt(R*p&c1,R*p&c2) THEN c1 = c1 | p
ELSE c2 = c2 | p FI;
v = v & -p
OD
RETURN c1
END.

```

Rudolf Berghammer - rub@informatik.uni-kiel.de
Last modified: 15-Aug-2012, 11:02:02 CEST