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

Makespan minimization in restricted assignment $(R|p_{ij}\in \{p_j,\infty\}|C_{\max})$ is a classical problem in the field of machine scheduling.In a landmark paper in 1990 [8], Lenstra, Shmoys, and Tardos gave a2-approximation algorithm and proved that the problem cannot be approximatedwithin 1.5 unless P=NP. The upper and lower bounds of the problem have beenessentially unimproved in the intervening 25 years, despite several remarkablesuccessful attempts in some special cases of the problem [2,4,12] recently.  In this paper, we consider a special case called graph-balancing with lighthyper edges, where heavy jobs can be assigned to at most two machines whilelight jobs can be assigned to any number of machines. For this case, we presentalgorithms with approximation ratios strictly better than 2. Specifically,  Two job sizes: Suppose that light jobs have weight $w$ and heavy jobs haveweight $W$, and $w < W$. We give a $1.5$-approximation algorithm (note that thecurrent 1.5 lower bound is established in an even more restrictive setting[1,3]). Indeed, depending on the specific values of $w$ and $W$, sometimes ouralgorithm guarantees sub-1.5 approximation ratios.  Arbitrary job sizes: Suppose that $W$ is the largest given weight, heavy jobshave weights in the range of $(\beta W, W]$, where $4/7\leq \beta < 1$, andlight jobs have weights in the range of $(0,\beta W]$. We present a$(5/3+\beta/3)$-approximation algorithm.  Our algorithms are purely combinatorial, without the need of solving a linearprogram as required in most other known approaches.

A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges