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

Generalizing many well-known and natural scheduling problems, scheduling withjob-specific cost functions has gained a lot of attention recently. In thissetting, each job incurs a cost depending on its completion time, given by aprivate cost function, and one seeks to schedule the jobs to minimize the totalsum of these costs. The framework captures many important scheduling objectivessuch as weighted flow time or weighted tardiness. Still, the general case aswell as the mentioned special cases are far from being very well understoodyet, even for only one machine. Aiming for better general understanding of thisproblem, in this paper we focus on the case of uniform job release dates on onemachine for which the state of the art is a 4-approximation algorithm. This istrue even for a special case that is equivalent to the covering version of thewell-studied and prominent unsplittable flow on a path problem, which isinteresting in its own right. For that covering problem, we present aquasi-polynomial time $(1+\epsilon)$-approximation algorithm that yields an$(e+\epsilon)$-approximation for the above scheduling problem. Moreover, forthe latter we devise the best possible resource augmentation result regardingspeed: a polynomial time algorithm which computes a solution with \emph{optimal}cost at $1+\epsilon$ speedup. Finally, we present an elegant QPTAS for thespecial case where the cost functions of the jobs fall into at most $\log n$many classes. This algorithm allows the jobs even to have up to $\log n$ manydistinct release dates.

How Unsplittable-Flow-Covering helps Scheduling with Job-Dependent Cost Functions