Abstract
Given a collection of multisets \(\{X_1, X_2, \ldots , X_k\}\) (\(k \ge 2\)) of positive integers, a multiset \(S\) is a common integer partition for them if \(S\) is an integer partition of every multiset \(X_i, 1 \le i \le k\). The minimum common integer partition (\(k\)-MCIP) problem is defined as to find a CIP for \(\{X_1, X_2, \ldots , X_k\}\) with the minimum cardinality. We present a \(\frac{6}{5}\)-approximation algorithm for the \(2\)-MCIP problem, improving the previous best algorithm of ratio \(\frac{5}{4}\) designed in 2006. We then extend it to obtain an absolute \(0.6k\)-approximation algorithm for \(k\)-MCIP when \(k\) is even (when \(k\) is odd, the approximation ratio is \(0.6k+0.4\)).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithm, and Applications. China Machine Press (2005)
Andrews, G.: The Theory of Partitions. Addison-Wesley (1976)
Andrews, G., Eriksson, K.: The Integer Partitions. Cambridge University Press (2004)
Berman, P.: A \(d\)/2 approximation for maximum weight independent set in \(d\)-claw free graphs. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 214–219. Springer, Heidelberg (2000)
Chen, X., Liu, L., Liu, Z., Jiang, T.: On the minimum common integer partition problem. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 236–247. Springer, Heidelberg (2006)
Chen, X., Liu, L., Liu, Z., Jiang, T.: On the minimum common integer partition problem. ACM Transactions on Algorithms 5, Article 12 (2008)
Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., Jiang, T.: The assignment of orthologous genes via genome rearrangement. IEEE/ACM Transactions on Computational Biololgy and Bioinformatics 2, 302–315 (2005)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)
Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters 37, 27–35 (1991)
Woodruff, D.P.: Better approximations for the minimum common integer partition problem. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol. 4110, pp. 248–259. Springer, Heidelberg (2006)
Zhao, W., Zhang, P., Jiang, T.: A network flow approach to the minimum common integer partition problem. Theoretical Computer Science 369, 456–462 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Tong, W., Lin, G. (2014). An Improved Approximation Algorithm for the Minimum Common Integer Partition Problem. In: Ahn, HK., Shin, CS. (eds) Algorithms and Computation. ISAAC 2014. Lecture Notes in Computer Science(), vol 8889. Springer, Cham. https://doi.org/10.1007/978-3-319-13075-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-13075-0_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13074-3
Online ISBN: 978-3-319-13075-0
eBook Packages: Computer ScienceComputer Science (R0)