{************************************************************ 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.