Reverse 1-median problem under Hamming distance

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (19): 39-41.

• 研究、探讨 • Previous Articles Next Articles

Reverse 1-median problem under Hamming distance

BAI Yanqin，WANG Qin，WU Longshu

Department of Mathematics，School of Sciences，China Jiliang University，Hangzhou 310018，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-01 Published:2011-07-01

哈明距离下1-重心问题的反问题

白艳琴，王勤，吴龙树

中国计量学院理学院数学系，杭州 310018

Abstract

Abstract: This paper mainly discusses the reverse 1-median problem under the Hamming distance.The reverse 1-median problem is to reduce the overall sum of the weighted distances from the vertices to a given vertex by changing the parameters in a network such that it can satisfy a given budget，and the cost for changing the parameters is as small as possible.Under the hamming distance，it shows that this problem is NP-hard.By using dynamic programming method，this problem is solved in a general network by changing the weights of vertices.

Key words: 1-median, Hamming distance, reverse problem, dynamic programming, NP-hard

摘要： 主要讨论哈明距离下网络中的1-重心问题的反问题。1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值，使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界。证明了在哈明距离下该问题是NP困难的。并运用动态规划的思想，在考虑改变顶点的权的情况下，对一般网络进行了求解。

关键词: 1-重心, 哈明距离, 反问题, 动态规划, NP困难

BAI Yanqin，WANG Qin，WU Longshu. Reverse 1-median problem under Hamming distance[J]. Computer Engineering and Applications, 2011, 47(19): 39-41.

白艳琴，王勤，吴龙树. 哈明距离下1-重心问题的反问题[J]. 计算机工程与应用, 2011, 47(19): 39-41.

[1]	FAN Jianping, CHENG Rui, WU Meiqin. Distance Measure of Interval-Valued Complex Fuzzy Soft Sets and Its Application [J]. Computer Engineering and Applications, 2020, 56(9): 248-259.
[2]	ZHOU Ruimin, LI Hui. Path Planning of Mobile Robot Based on Improved Dynamic Programming Algorithm [J]. Computer Engineering and Applications, 2020, 56(21): 20-24.
[3]	CHEN Junjie, TONG Shurong, NIE Yafei, ZHANG Jingwen. R&D Program Scheduling and Staff Assignment with Hierarchical Levels of Competency [J]. Computer Engineering and Applications, 2019, 55(3): 209-218.
[4]	LIAN Wei. Globally Optimal Shape Matching Algorithm Using Tree Representation [J]. Computer Engineering and Applications, 2019, 55(1): 217-225.
[5]	ZHANG Yu, CUI Yaodong, LIANG Zehua. Two-dimensional cutting stock problem of multiple logs [J]. Computer Engineering and Applications, 2018, 54(19): 266-270.
[6]	XIAO Hongde. Calculation of minimum count of money and determination of money denomination [J]. Computer Engineering and Applications, 2018, 54(16): 266-270.
[7]	SUN Peishuang, HAN Qirui. Improved optimal stitching line applied to image stitching [J]. Computer Engineering and Applications, 2016, 52(21): 218-221.
[8]	FANG Gang1, ZHANG Shemin2. 3-gram statistical language model optimization to expression vector design [J]. Computer Engineering and Applications, 2016, 52(15): 60-64.
[9]	ZHANG Xingong, WANG Hui, BAI Shikun. Two-agent scheduling on single machine to minimize number of tardy jobs [J]. Computer Engineering and Applications, 2016, 52(14): 32-36.
[10]	LI Huiguang, LI Feng, SHAO Nuan, SHA Xiaopeng, WANG Shuai. Segment-based stereo matching method with ground control points [J]. Computer Engineering and Applications, 2015, 51(23): 160-163.
[11]	ZHANG Yu, XU Hongze, CHEN Jianqiang,ZHANG Luning. Research on optimization strategy of train route control in metallurgical enterprises [J]. Computer Engineering and Applications, 2015, 51(17): 250-254.
[12]	SHEN Lu1，2, JI Yun1, JI Dongbao3, LI Ping4. Pattern matching with variable length wildcards [J]. Computer Engineering and Applications, 2015, 51(15): 43-47.
[13]	WANG Jun. Dynamic programming and tabu search hybrid algorithm for Vehicle Routing Problem with fuzzy time windows [J]. Computer Engineering and Applications, 2014, 50(24): 58-64.
[14]	ZHAO Xu, WANG Wei. Optimization research of DSAMDP method with dynamic programming theory [J]. Computer Engineering and Applications, 2014, 50(22): 83-87.
[15]	ZENG Qiang1, SHEN Ling2, WU Liyun1, LAN Jianyi1. Improved method to optimize aggregate production planning based on dynamic programming [J]. Computer Engineering and Applications, 2014, 50(21): 248-253.

Reverse 1-median problem under Hamming distance

哈明距离下1-重心问题的反问题

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics