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/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider single-machine scheduling problems that are naturalgeneralizations or variations of the min-sum set cover problem and the min-sumvertex cover problem. For each of these problems, we give new approximationalgorithms. Some of these algorithms rely on time-indexed LP relaxations. Weshow how a variant of alpha-point scheduling leads to the best-knownapproximation ratios, including a guarantee of 4 for an interesting specialcase of the so-called generalized min-sum set cover problem. We also makeexplicit the connection between the greedy algorithm for min-sum set cover andthe concept of Sidney decomposition for precedence-constrained single-machinescheduling, and show how this leads to a 4-approximation algorithm forsingle-machine scheduling with so-called bipartite OR-precedence constraints.

Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover