首页 | 本学科首页   官方微博 | 高级检索  
     


Euclidean movement minimization
Authors:Nima Anari  MohammadAmin Fazli  Mohammad Ghodsi  MohammadAli Safari
Affiliation:1.Computer Science Division,University of California Berkeley,Berkeley,USA;2.Department of Computer Engineering,Sharif University of Technology,Tehran,Iran;3.Institute of Research in Fundamental Sciences (IPM),Tehran,Iran
Abstract:
We consider a class of optimization problems called movement minimization on euclidean plane. Given a set of (m) nodes on the plane, the aim is to achieve some specific property by minimum movement of the nodes. We consider two specific properties, namely the connectivity (Con) and realization of a given topology (Topol). By minimum movement, we mean either the sum of all movements (Sum) or the maximum movement (Max). We obtain several approximation algorithms and some hardness results for these four problems. We obtain an (O(m))-factor approximation for ConMax and ConSum and extend some known result on graphical grounds and obtain inapproximability results on the geometrical grounds. For the Topol problems (where the final decoration of the nodes must correspond to a given configuration), we find it much simpler and provide FPTAS for both Max and Sum versions.
Keywords:
本文献已被 SpringerLink 等数据库收录!
相似文献(共20条):
[1]、Chen,Cong,Zhang,Huili,Xu,Yinfeng.Online machine minimization with lookahead[J].Journal of Combinatorial Optimization,2022,43(5):1149-1172.
[2]、Yu-Ping Tsao,Gerard J. Chang.Profile minimization on compositions of graphs[J].Journal of Combinatorial Optimization,2007,14(2-3):177-190.
[3]、Edem O. P. Akpan.Resource smoothing: A cost minimization approach[J].生产规划与管理,2013,24(8):775-780.
[4]、Maximum lateness minimization in one-dimensional bin packing[J].Omega
[5]、Liang Song,Hejiao Huang,Hongwei Du.Approximation schemes for Euclidean vehicle routing problems with time windows[J].Journal of Combinatorial Optimization,2016,32(4):1217-1231.
[6]、Fubin Qian,Irina Gribkovskaia.Passenger and pilot risk minimization in offshore helicopter transportation[J].Omega,2012,40(5):584-593.
[7]、Chen Liao,Shiyan Hu.Approximation scheme for restricted discrete gate sizing targeting delay minimization[J].Journal of Combinatorial Optimization,2011,21(4):497-510.
[8]、Efficient composite heuristics for total flowtime minimization in permutation flow shops[J].Omega
[9]、Jueliang Hu,Yiwei Jiang,Ping Zhou,An Zhang,Qinghui Zhang.Total completion time minimization in online hierarchical scheduling of unit-size jobs[J].Journal of Combinatorial Optimization,2017,33(3):866-881.
[10]、Quan-Ke Pan,Ling Wang.Effective heuristics for the blocking flowshop scheduling problem with makespan minimization[J].Omega,2012,40(2):218-229.
[11]、Mirhadi,S. M.,MirHassani,S. A..A solution approach for cardinality minimization problem based on fractional programming[J].Journal of Combinatorial Optimization,2022,44(1):583-602.
[12]、Makespan and workstation utilization minimization in a flowshop with operations flexibility[J].Omega
[13]、Adam Janiak,RadosŁaw Rudek.A note on a makespan minimization problem with a multi-ability learning effect[J].Omega,2010,38(3-4):213-217.
[14]、Dbora P. Ronconi,Luís R.S. Henriques.Some heuristic algorithms for total tardiness minimization in a flowshop with blocking[J].Omega,2009,37(2):272-281.
[15]、Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints[J].Omega
[16]、Minming Li,Tiantian Liu,Chun Jason Xue,Yingchao Zhao.Analysis and approximation for bank selection instruction minimization on partitioned memory architecture[J].Journal of Combinatorial Optimization,2012,23(2):274-291.
[17]、Neng Fan,Panos M. Pardalos.A rearrangement of adjacency matrix based approach for solving the crossing minimization problem[J].Journal of Combinatorial Optimization,2011,22(4):747-762.
[18]、Lixing Yang,Keping LiZiyou Gao,Xiang Li.Optimizing trains movement on a railway network[J].Omega,2012,40(5):619-633.
[19]、Karunakaran Chakravarthy,Chandrasekharan Rajendran.A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization[J].生产规划与管理,2013,24(7):707-714.
[20]、Bruce Tranter,.Leadership and change in the Tasmanian environment movement[J].The Leadership Quarterly,2009,20(5):708-724.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号