Scholarlink

Abstract <p> The Uncapacitated Facility Location Problem is a well-known discrete optimization problem. We consider a problem with unsplittable demands and without triangle inequality. This problem is NP-hard in the strong sense. We propose a primal-dual approximate polynomial algorithm with a posteriori performance guarantee. The approach comprises two polynomial approximation algorithms: <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal A_1\)</EquationSource> </InlineEquation>, which utilises the greedy heuristic, and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\mathcal A_2\)</EquationSource> </InlineEquation>, as proposed by the authors, based on identifying the dead-end solution to the dual problem. The complexity of the proposed algorithm is <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\mathcal O(mn(m + \log n))\)</EquationSource> </InlineEquation>, where <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(m\)</EquationSource> </InlineEquation> is the number of facilities and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(n\)</EquationSource> </InlineEquation> is the number of customers. In the dual algorithm, a binary heap is used, which significantly reduces the actual runtime of the algorithm. The reduction in runtime is especially noticeable on high-dimensional instances. Numerical experiments with randomly generated instances demonstrate the effectiveness of the proposed algorithms through their computational results. </p>

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

A Primal-Dual Polynomial Approximation Algorithm for the Uncapacitated Facility Location Problem

  • 期刊论文

  • 发表日期：

    2025年12月1日

查看全文
  • E. Kh. Gimadi,
  • E. N. Goncharov,
  • A. A. Shtepa

摘要

Abstract

The Uncapacitated Facility Location Problem is a well-known discrete optimization problem. We consider a problem with unsplittable demands and without triangle inequality. This problem is NP-hard in the strong sense. We propose a primal-dual approximate polynomial algorithm with a posteriori performance guarantee. The approach comprises two polynomial approximation algorithms: \(\mathcal A_1\) , which utilises the greedy heuristic, and \(\mathcal A_2\) , as proposed by the authors, based on identifying the dead-end solution to the dual problem. The complexity of the proposed algorithm is \(\mathcal O(mn(m + \log n))\) , where \(m\) is the number of facilities and \(n\) is the number of customers. In the dual algorithm, a binary heap is used, which significantly reduces the actual runtime of the algorithm. The reduction in runtime is especially noticeable on high-dimensional instances. Numerical experiments with randomly generated instances demonstrate the effectiveness of the proposed algorithms through their computational results.