A linear approximation algorithm for bin packing with absolute approximation factor 3/2

Rudolf Berghammer; Florian Reuter

首页> 外文期刊>Science of Computer Programming >A linear approximation algorithm for bin packing with absolute approximation factor 3/2

【24h】

A linear approximation algorithm for bin packing with absolute approximation factor 3/2

机译：绝对近似系数为3/2的装箱装箱的线性近似算法

获取原文

获取原文并翻译 | 示例

开具论文收录证明 >>

页面导航

摘要
著录项
引文网络
相似文献
相关主题

摘要

We present a new approximation algorithm for the bin packing problem which has a linear running time and an absolute approximation factor of 3/2. It is known that this approximation factor is the best factor achievable, unless P = NP.

机译：对于箱装问题，我们提出了一种新的近似算法，该算法具有线性运行时间和3/2的绝对近似因子。众所周知，除非P = NP，否则该近似因子是可获得的最佳因子。

著录项

来源
《Science of Computer Programming》 |2003年第1期|p.67-80|共14页
作者
Rudolf Berghammer; Florian Reuter;
展开▼
作者单位

Institut fuer Informatik und Praktische Mathematik, Christian-Albrechts-Universitaet Kiel, Olshausenstrasse 40, D-24098 Kiel, Germany;

展开▼
收录信息美国《科学引文索引》(SCI);美国《工程索引》(EI);
原文格式 PDF
正文语种 eng
中图分类计算机软件;
关键词
bin packing; approximation algorithm; formal program development;

机译：垃圾箱包装;近似算法正式程序开发;

相似文献

外文文献
中文文献
专利

1. Linear time-approximation algorithms for bin packing [J] . Zhang GC., Wong CK., Cai XQ. Operations Research Letters: A Journal of the Operations Research Society of America . 2000,第5期

机译：用于装箱的线性时间近似算法
2. Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems [J] . Mingen Lin, Yang Yang, Jinhui Xu Algorithmica . 2010,第2期

机译：改进的近似算法，用于最大资源箱打包和惰性箱覆盖问题
3. Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems [J] . Mingen Lin, Yang Yang, Jinhui Xu Algorithmica . 2010,第2期

机译：改进的近似算法，用于最大资源箱打包和惰性箱覆盖问题
4. Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems [C] . Mingen Lin, Yang Yang, Jinhui Xu Algorithms and Computation; Lecture Notes in Computer Science; 4288 . 2006

机译：改进的近似算法，用于最大资源箱打包和惰性箱覆盖问题
5. Optimization algorithms based on conic approximations and collinear scalings. [D] . Begashaw, Negash. 1997

机译：基于圆锥近似和共线缩放的优化算法。
6. Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations [O] . Xuefei Shi, Dehua Xu -1

机译：线性维护持续时间增加的单机调度的最佳近似算法
7. A linear approximation algorithm for bin packing with absolute approximation factor 32 [O] . Berghammer Rudolf, Reuter Florian 2003

机译：具有绝对逼近因子32的装箱的线性逼近算法
8. A Dual Algorithm to Solve Linear Least Absolute Value Approximations [R] . Armstrong, R., Kung, M. 1980

机译：一种求解线性最小绝对值近似的对偶算法

A linear approximation algorithm for bin packing with absolute approximation factor 3/2

摘要

著录项

引文网络

相似文献

相关主题

期刊订阅