Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix

Fang  Tian; Zi-Long  Liu

doi:10.3934/jimo.2016.12.1249

Article Contents

2016, Volume 12, Issue 4: 1249-1265. Doi: 10.3934/jimo.2016.12.1249

This issue Previous Article Circulant tensors with applications to spectral hypergraph theory and stochastic process Next Article Stability analysis of a delayed social epidemics model with general contact rate and its optimal control

Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix

Fang Tian^1, and
Zi-Long Liu^2,

1.
Department of Applied Mathematics, Shanghai University of Finance and Economics, Shanghai 200433
2.
School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093

Received: November 30, 2013

Revised: September 30, 2015

Published: September 2016

Abstract Related Papers Cited by

Abstract

$2$-CatSP is a fundamental NP-Complete optimization problem, which is formulated as given a ground set $U$ of $n$ items, $m$ subsets $S_1,S_2,\cdots,$ $S_m$ of $U$ and an integer $1\leq t\leq n$, find two subsets $A_1$ and $A_2$ of $U$ such that $|A_1|=|A_2|\leq t$ and $\sum_{i=1}^{m}\max\left(|S_i\cap A_1|,|S_i\cap A_2|\right)$ is maximized. In this paper, we reconsider randomized approximation algorithms for $2$-CatSP without and with triangle inequalities in terms of a new positive semidefinite matrix reflecting more information on unbalanced properties. The performance ratios of our algorithm are much better than the current best ones of Xu et al in (Optim. Method. Softw., 18(6): 705-719, 2003) for general cases under unbalanced parameters $\sigma=t/n\geq 0.50$ by our rigorous analysis. In particular, we get 0.6700 and 0.7250 without and with triangle inequalities for the most important subcase $\sigma=0.50$, improving previously best ratios 0.6430 and 0.6736 in corresponding environment. Indeed recently Wu et al (J. Ind. Manag. Optim. 8: 117-126, 2012) and Xu et al in (J. Comb. Optim., 27: 315-327, 2014) also considered approximate strategies for its disjoint subcase $A_1\cap A_2=\emptyset$ as $\sigma=0.50$ with ratios 0.7317 and 0.7469, which can be reduced to max bisection problems of graphs.

Keywords:

Mathematics Subject Classification: Primary: 90C25, 90C27; Secondary: 68Q25, 68W25.

Citation:

Related Papers

Cited by

References

[1]	A. Amiri, Customer-oriented catalog segmentation: Effective solution approaches, Decision Support Syst., 42 (2006), 1860-1871.doi: 10.1016/j.dss.2006.04.010.
[2]	S. Arora, S. Rao and U. Vazirani, Expander flows, geometric embeddings and graph partitioning, in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, 222-231.doi: 10.1145/1007352.1007355.
[3]	P. Austrin, Balanced max 2-sat might not be the hardest, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, 189-197.doi: 10.1145/1250790.1250818.
[4]	B. Barak, P. Raghavendra and D. Steurer, Rounding semidefinite programming hierarchies via global correlation, FOCS, (2011), 472-481.doi: 10.1109/FOCS.2011.95.
[5]	D. Bertsimas and Y. Ye, Semidenite relaxations, multivariate normal distributions, and order statistics, Handbook of Combinatorial Optimization, 3 (1998), 1-19.doi: 10.1016/S1386-4181(97)00012-8.
[6]	Y. Dodis, V. Guruswami and S. Khanna, The $2$-catalog segmentation problem, in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, 897-898.
[7]	M. Ester, R. Ge, W. Jin and Z. Hu, A microeconomic data mining problem: Customer-oriented catalog segmentation, in Proceedings of 10th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining, 2004, 557-562.
[8]	U. Feige and M. X. Goemans, Approximating the value of two prover proof systems, with applications to max $2$sat and max dicut, in Proceedings of the 3rd Israel Symposium on Theory and Computing Systems, 1995, 182-189.
[9]	U. Feige and M. Langberg, Approximation algorithms for maximization problems in graph partitioning, J. Algorithm, 41 (2001), 174-211.doi: 10.1006/jagm.2001.1183.
[10]	U. Feige, Relations between average case complexity and approximation complexity, in Proceedings on 34th Annual ACM Symposium on Theory and Computing, 2002, 534-543.doi: 10.1145/509907.509985.
[11]	U. Feige and M. Langberg, The $RPR^2$ rounding technique for semidefinite programs, J. Algorithm, 60 (2006), 1-23.doi: 10.1016/j.jalgor.2004.11.003.
[12]	A. Frieze and M. Jerrum, Improved approximation algorithms for max $k$-cut and max bisection, Algorithmica, 18 (1997), 67-81.doi: 10.1007/BF02523688.
[13]	G. Galbiati and F. Maffioli, Approximation algorithms for maximum cut with limited unbalance, Theor. Comput. Sci., 385 (2007), 78-87.doi: 10.1016/j.tcs.2007.05.036.
[14]	M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), 1115-1145.doi: 10.1145/227683.227684.
[15]	V. Guruswami and A. Sinop, Lasserre hierarchy, higher eigenvalues, and approximation schemes for quadratic integer programming with psd objectives, FOCS, (2011), 482-491.doi: 10.1109/FOCS.2011.36.
[16]	E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Structures and Algorithms, 20 (2002), 382-402.doi: 10.1002/rsa.10035.
[17]	Q. Han, Y. Ye and J. Zhang, An improved rounding method and semidefinite programming relaxation for graph partition, Math. Program. Ser. A, 92 (2002), 509-535.doi: 10.1007/s101070100288.
[18]	Q. Han, Y. Ye, H. Zhang and J. Zhang, On approximation of max-vertex-cover, Eur. J. Oper. Res., 143 (2002), 342-355.doi: 10.1016/S0377-2217(02)00330-2.
[19]	C. Helmberg, Cutting Planes Algorithm for Large Scale Semidefinite Relaxations, ZIB-Report ZR 01-26, Konrad-Zuse-Zentrum fuer Informationstechnik Berlin, Takustrasse 7, D-14195 Berlin, Germany, Oct., 2001.
[20]	M. Iraj, M. Mahyar and A. Fereydoun, Designing customer-oriented catalogs in e-CRM using an effective self-adaptive genetic algorithm, Expert Systems with Applications, 38 (2011), 631-639.
[21]	S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for max-cut and other 2-variable csps, SIAM J. Comput., 37 (2007), 319-357.doi: 10.1137/S0097539705447372.
[22]	J. Kleinberg, C. Papadimitriou and P. Raghavan, A microeconomic view of data mining, Data Mining and Knowledge Discovery, 2 (1998), 311-324.
[23]	J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems, J. ACM, 51 (2004), 263-280.doi: 10.1145/972639.972644.
[24]	J. Löfberg, YALMIP: A toolbox for modelling and optimization in matlab, in Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
[25]	Z. Q. Luo, N. D. Sidiropoulos, P. Tseng and S.-Z. Zhang, Approximation bounds for quadratic optimization with homogeneous quadratic constraints, SIAM J. Optimiz., 18 (2007), 1-28.doi: 10.1137/050642691.
[26]	P. Raghavendra, Optimal algorithms and inapproximability results for every csp, in Proceedings of the 40th ACM Symposium on Theory of Computing, 2008, 245-254.doi: 10.1145/1374376.1374414.
[27]	P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies, SODA, (2012), 373-384.
[28]	F. Roupin, From linear to semidefinite programming: An algorithm to obtain semidefinite relaxations for bivalent quadratic problems, J. Comb. Optim., 8 (2004), 469-493.doi: 10.1007/s10878-004-4838-6.
[29]	R. Saket, Quasi-Random PCP and hardness of $2$-catalog segmentation, Foundations of Software Technology and Theoretical Computer Science-FSTTCS, 8 (2010), 447-458.
[30]	L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95.doi: 10.1137/1038003.
[31]	C. Wu, D. Xu and X. Zhao, An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation, J. Ind. Manag. Optim., 8 (2012), 117-126.
[32]	D. Xu, Y. Ye and J Zhang, A note on approximating the 2-catalog segmentation problem, Working Paper,Department of Management Sciences, Henry, B Tippie College of Business, The University of Iowa, Iowa City, IA, 52242, USA.
[33]	D. Xu, Y. Ye and J. Zhang, Approximate the $2$-catalog segmentation problem using semidefinite programming relaxations, Optim. Method. and Softw., 18 (2003), 705-719.doi: 10.1080/10556780310001634082.
[34]	D. Xu, J. Han, Z. Huang and L. Zhang, Improved approximation algorithms for Max-directed-bisection and Max-dense-subgraph, J. Global Optim., 27 (2003), 399-410.doi: 10.1023/A:1026094110647.
[35]	D. Xu, J. Han and D. Du, Approximation of dense-$\fracn{2}$-subgraph and table compression problems, Science in China Ser. A: Mathematics, 48 (2005), 1223-1233.doi: 10.1360/04ys0167.
[36]	D. Xu and S. Zhang, Approximation bounds for quadratic maximization and max-cut problem with semidefinite programming relaxation, Science in China Ser. A: Mathematics, 50 (2007), 1583-1596.doi: 10.1007/s11425-007-0080-x.
[37]	Z. Xu, D. Du and D. Xu, Improved approximation algorithms for the max-bisection and the disjoint $2$ catalog segmentation problems, J. Comb. Optim., 27 (2014), 315-327.doi: 10.1007/s10878-012-9526-3.
[38]	Y. Ye, A.699-approximation algorithm for max-bisection, Math. Program. Ser. A, 90 (2001), 101-111.doi: 10.1007/PL00011415.
[39]	Y. Ye and J. Zhang, Approximation of dense-$\fracn{2}$-subgraph and the complement of min-bisection, J. Global Optim., 25 (2003), 55-73.doi: 10.1023/A:1021390231133.
[40]	J. Zhang, Y. Ye and Q. Han, Improved approximations for max set splitting and max NAE SAT, Discrete Appl. Math., 142 (2004), 133-149.doi: 10.1016/j.dam.2002.07.001.