A two-phase method for multidimensional  number partitioning problem

Feng  Ma; Mingfang Ni

doi:10.3934/naco.2013.3.203

Article Contents

2013, Volume 3, Issue 2: 203-206. Doi: 10.3934/naco.2013.3.203

This issue Previous Article Preface Next Article Partial eigenvalue assignment with time delay robustness

A two-phase method for multidimensional number partitioning problem

Feng Ma^1, and
Mingfang Ni^1,

1.
Institute of Communications Engineering, PLA University of Science and Technology, Nanjing, 210007

Received: October 2011

Revised: December 2012

Published online: April 2013

Abstract / Introduction Related Papers Cited by

Abstract

The multidimensional number partitioning problem is to split a given set of integer vectors into two disjoint subsets, such that the sums of the elements in the two subsets are equal or nearly equal on every coordinate. This partitioning problem is in fact NP-hard. In this paper, we propose an optimization method for this problem. The proposed method involves recasting the original problem as a two-phase optimization problem. First, candidate partitions are obtained by using the method proposed in [4]. Then the optimal one is selected from the obtained candidate partitions. An example is given to illustrate the method.

Keywords:

Mathematics Subject Classification: Primary: 90C10, 05A18; Secondary: 65K05.

Citation:

Related Papers

Cited by

References

[1]	M. Diaby, Linear programming formulation of the set partitioning problem, Int. J. Operational Research, 8 (2010), 399-427.
[2]	M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," W. H. Freeman, New York, 1979.
[3]	N. Karmarkar and R. M. Karp, The differencing method of set partitioning, Technical Report UCB/CSD 82/113, Computer Science Division, University of California, Berkeley, (1982).
[4]	J. Kojić, Integer linear programming model for multidimensional two-way number partitioning problem, Computer and Mathematics with Applications, 60 (2010), 2302-2308.doi: 10.1016/j.camwa.2010.08.024.
[5]	R. E. Korf, Multi-way number partitioning, in "Proceedings of Proceedings of the International Joint Conference on Artificial Intelligence," Pasadena, California, USA, (2009), 538-543.
[6]	R. E. Korf, Objective functions for multi-way number partitioning, in "Proceedings of the Third Annual Symposium on Combinatorial Search," Atlanta, Georgia, USA, 2010, Available from: http://www.aaai.org/ocs/index.php/SOCS/SOCS10/paper/view/2098.
[7]	R. E. Korf, A complete anytime algorithm for number partitioning, Artificial Intelligence, 106 (1998), 181-203.doi: 10.1016/S0004-3702(98)00086-1.
[8]	R. E. Korf, From approximate to optimal solutions: A case study of number partitioning, in "Proceedings of Proceedings of the International Joint Conference on Artificial Intelligence," Montreal, Canada, (1995), 266-272.
[9]	M. S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programming, Linear Algebra and its Applications, 284 (1998), 193-228.doi: 10.1016/S0024-3795(98)10032-0.