...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >NP-hardness of the sorting buffer problem on the uniform metric
【24h】

NP-hardness of the sorting buffer problem on the uniform metric

机译：均匀度量下排序缓冲区问题的NP硬度

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

An instance of the sorting buffer problem (SBP) consists of a sequence of requests for service, each of which is specified by a point in a metric space, and a sorting buffer which can store up to a limited number of requests and rearrange them. To serve a request, the server needs to visit the point where serving a request p following the service to a request q requires the cost corresponding to the distance d(p,q) between p and q. The objective of SBP is to serve all input requests in a way that minimizes the total distance traveled by the server by reordering the input sequence. In this paper, we focus our attention to the uniform metric, i.e., the distance d(p,q)=1 if p≠q, d(p,q)=0 otherwise, and present the first NP-hardness proof for SBP on the uniform metric.
机译：排序缓冲区问题（SBP）的一个实例包括一系列服务请求，每个请求由度量空间中的一个点指定，以及一个排序缓冲区，该缓冲区最多可以存储有限数量的请求并重新排列它们。为了满足请求，服务器需要访问服务于请求之后的请求p到请求q的点需要与p和q之间的距离d（p，q）相对应的成本。 SBP的目的是通过重新排序输入序列，以最小化服务器行进的总距离的方式满足所有输入请求。在本文中，我们将注意力集中在统一度量上，即如果p≠q，则距离d（p，q）= 1，否则，d（p，q）= 0，并提出用于SBP的第一个NP硬度证明。在统一指标上

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号