Scholarlink

<p>We consider the capacitated facility location problem with outliers when facility costs are uniform. Our main result is the first constant factor approximation for this problem. We give a local search algorithm that requires only 2 operations and is a 6.373 +<InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\epsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation> approximation. In developing this result we also improve the approximation guarantee of the capacitated facility location problem with uniform facility costs. Our local search algorithm is extremely simple to analyze and is a 3.733+<InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\epsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>- approximation thus improving on the 4-approximation of &#xa0;Kao [<CitationRef CitationID="CR2">2</CitationRef>].</p>

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

Capacitated facility location with outliers and uniform facility costs

  • 期刊论文

  • 发表日期：

    2025年7月17日

查看全文
  • Neelima Gupta,
  • Rajni Dabas,
  • Naveen Garg

摘要

We consider the capacitated facility location problem with outliers when facility costs are uniform. Our main result is the first constant factor approximation for this problem. We give a local search algorithm that requires only 2 operations and is a 6.373 + \(\epsilon \) ϵ approximation. In developing this result we also improve the approximation guarantee of the capacitated facility location problem with uniform facility costs. Our local search algorithm is extremely simple to analyze and is a 3.733+ \(\epsilon \) ϵ - approximation thus improving on the 4-approximation of  Kao [2].