2012/07/24 by György Dósa, Gyorgy Dosa, Dosa, Gyorgy +3
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems #Scheduling and Optimization Algorithms #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1207.5672
16 pages
arxiv created 2012/07/24 · openalex publication_date 2012/07/24 · arxiv updated 2015/03/20 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
In the recent paper \citeBDT10 we introduced a new problem that we call Bin Packing/Covering with Delivery, or BP/CD for short. Mainly we mean under this expression that we look for not only a good, but a "good and fast" packing or covering. In that paper we mainly dealt with only one possible online BP/CD model, and proposed a new method that we call the Evolution of Algorithms. In case of such methods a neighborhood structure is defined among algorithms, and using a metaheuristic (for example simulated annealing) in some sense the best algorithm is chosen to solve the problem. Now we turn to investigate the offline case. We define several ways to treat such a BP/CD problem, although we investigate only one of them here. For the analysis, a novel view on "offline optimum" is introduced, which appears to be relevant concerning all problems where a final solution is ordering-dependent. We prove that if the item sizes are not allowed to be arbitrarily close to zero, then an optimal offline solution can be found in polynomial time. On the other hand, for unrestricted problem instances, no polynomial-time algorithm can achieve an approximation ratio better than 6/7 if P≠ NP.