Seminário de Teoria da Computação

 Greedy Approximated Algorithm for the Uniform Labeling Problem

           Evandro C. Bracht e Luis A. A. Meira

           Sexta-feira, 24 de outubro de 2003

              Auditório do IC (IC1), 13:00hs

In this talk we present a new algorithm for the uniform metric
labeling problem.  This problem consists to assign objects to labels,
each object assigned to a label incur in an assignment cost and two
objects with distinct labels incur in a separation cost. The objective
function is to obtain an labeling that minimizes the total assignment
and separation cost. The known approximation algorithms are based on
solutions of large linear programs and are impractical for moderated
and large size instances. We present a $8\log n$-approximation
algorithm which, although has factor greater than the previous
algorithms, it can be applied to large size instances.  The algorithm
is greedy and is analyzed by a primal-dual technique. We use this
technique and redesign the traditional greedy algorithm for the Set
Cover problem, resulting in a very didactic example.