Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Primal-dual approximation algorithms for a packing-covering pair of problems

Sofia KovalevaFrits C. R. Spieksma — 2002

RAIRO - Operations Research - Recherche Opérationnelle

We consider a special packing-covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing problem and...

Primal-dual approximation algorithms for a packing-covering pair of problems

Sofia KovalevaFrits C.R. Spieksma — 2010

RAIRO - Operations Research

We consider a special packing-covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing problem and...

Page 1

Download Results (CSV)