English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

We consider a special packing-covering pair of problems. The packing problem is a natural generalization of nding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of nding 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 to the covering problem that are within a factor of 2 of each other. Each of these results implies an approximative min- max result. For the general case of arbitrary weights and capacities we describe an LP-based (2 + )-approximation algorithm for the covering problem. Finally, we show that, unless P = NP, the covering problem cannot be approximated in polynomial time within arbitrarily good precision.

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