Scholarlink

<p>Coflow scheduling is a challenging optimization problem that underlies many data transmission and parallel computing applications. In this paper, we study the <i>indivisible</i> coflow scheduling problem on parallel identical machines with the objective to minimize the makespan, i.e., the completion time of the last flow. In our problem setting, the number of the input/output ports in each machine is a fixed constant, each port has a unit capacity, and all the flows inside a coflow should be scheduled on the same machine. We present a <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1325_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">\((2 + \epsilon )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mo>+</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation algorithm for the problem, for any <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1325_Article_IEq2.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(\epsilon &gt; 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo>&gt;</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, in which the number of machines can be either a fixed constant or part of the input.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Improved approximation algorithms for multiprocessor indivisible coflow scheduling

  • 期刊论文

  • 发表日期：

    2025年5月25日

查看全文
  • Mingyang Gong,
  • Guangting Chen,
  • Guohui Lin,
  • Bing Su

摘要

Coflow scheduling is a challenging optimization problem that underlies many data transmission and parallel computing applications. In this paper, we study the indivisible coflow scheduling problem on parallel identical machines with the objective to minimize the makespan, i.e., the completion time of the last flow. In our problem setting, the number of the input/output ports in each machine is a fixed constant, each port has a unit capacity, and all the flows inside a coflow should be scheduled on the same machine. We present a \((2 + \epsilon )\) ( 2 + ϵ ) -approximation algorithm for the problem, for any \(\epsilon > 0\) ϵ > 0 , in which the number of machines can be either a fixed constant or part of the input.