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

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

October 2016, 12(4): 1249-1265. doi: 10.3934/jimo.2016.12.1249

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, China
2.	School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China

Received December 2013 Revised October 2015 Published January 2016

Abstract
Related Papers

$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: approximation algorithm, Catalog segmentation, semidefinite relaxation, Lasserres SDP hierarchy., triangle inequality.

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

Citation: Fang Tian, Zi-Long Liu. Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1249-1265. doi: 10.3934/jimo.2016.12.1249

References:

[1]	A. Amiri, Customer-oriented catalog segmentation: Effective solution approaches,, Decision Support Syst., 42 (2006), 1860. doi: 10.1016/j.dss.2006.04.010. Google Scholar
[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. doi: 10.1145/1007352.1007355. Google Scholar
[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. doi: 10.1145/1250790.1250818. Google Scholar
[4]	B. Barak, P. Raghavendra and D. Steurer, Rounding semidefinite programming hierarchies via global correlation,, FOCS, (2011), 472. doi: 10.1109/FOCS.2011.95. Google Scholar
[5]	D. Bertsimas and Y. Ye, Semidenite relaxations, multivariate normal distributions, and order statistics,, Handbook of Combinatorial Optimization, 3 (1998), 1. doi: 10.1016/S1386-4181(97)00012-8. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[9]	U. Feige and M. Langberg, Approximation algorithms for maximization problems in graph partitioning,, J. Algorithm, 41 (2001), 174. doi: 10.1006/jagm.2001.1183. Google Scholar
[10]	U. Feige, Relations between average case complexity and approximation complexity,, in Proceedings on 34th Annual ACM Symposium on Theory and Computing, (2002), 534. doi: 10.1145/509907.509985. Google Scholar
[11]	U. Feige and M. Langberg, The $RPR^2$ rounding technique for semidefinite programs,, J. Algorithm, 60 (2006), 1. doi: 10.1016/j.jalgor.2004.11.003. Google Scholar
[12]	A. Frieze and M. Jerrum, Improved approximation algorithms for max $k$-cut and max bisection,, Algorithmica, 18 (1997), 67. doi: 10.1007/BF02523688. Google Scholar
[13]	G. Galbiati and F. Maffioli, Approximation algorithms for maximum cut with limited unbalance,, Theor. Comput. Sci., 385 (2007), 78. doi: 10.1016/j.tcs.2007.05.036. Google Scholar
[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. doi: 10.1145/227683.227684. Google Scholar
[15]	V. Guruswami and A. Sinop, Lasserre hierarchy, higher eigenvalues, and approximation schemes for quadratic integer programming with psd objectives,, FOCS, (2011), 482. doi: 10.1109/FOCS.2011.36. Google Scholar
[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. doi: 10.1002/rsa.10035. Google Scholar
[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. doi: 10.1007/s101070100288. Google Scholar
[18]	Q. Han, Y. Ye, H. Zhang and J. Zhang, On approximation of max-vertex-cover,, Eur. J. Oper. Res., 143 (2002), 342. doi: 10.1016/S0377-2217(02)00330-2. Google Scholar
[19]	C. Helmberg, Cutting Planes Algorithm for Large Scale Semidefinite Relaxations,, ZIB-Report ZR 01-26, (2001), 01. Google Scholar
[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. Google Scholar
[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. doi: 10.1137/S0097539705447372. Google Scholar
[22]	J. Kleinberg, C. Papadimitriou and P. Raghavan, A microeconomic view of data mining,, Data Mining and Knowledge Discovery, 2 (1998), 311. Google Scholar
[23]	J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems,, J. ACM, 51 (2004), 263. doi: 10.1145/972639.972644. Google Scholar
[24]	J. Löfberg, YALMIP: A toolbox for modelling and optimization in matlab,, in Proceedings of the CACSD Conference, (2004). Google Scholar
[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. doi: 10.1137/050642691. Google Scholar
[26]	P. Raghavendra, Optimal algorithms and inapproximability results for every csp,, in Proceedings of the 40th ACM Symposium on Theory of Computing, (2008), 245. doi: 10.1145/1374376.1374414. Google Scholar
[27]	P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, SODA, (2012), 373. Google Scholar
[28]	F. Roupin, From linear to semidefinite programming: An algorithm to obtain semidefinite relaxations for bivalent quadratic problems,, J. Comb. Optim., 8 (2004), 469. doi: 10.1007/s10878-004-4838-6. Google Scholar
[29]	R. Saket, Quasi-Random PCP and hardness of $2$-catalog segmentation,, Foundations of Software Technology and Theoretical Computer Science-FSTTCS, 8 (2010), 447. Google Scholar
[30]	L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. doi: 10.1137/1038003. Google Scholar
[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. Google Scholar
[32]	D. Xu, Y. Ye and J Zhang, A note on approximating the 2-catalog segmentation problem,, Working Paper, (5224). Google Scholar
[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. doi: 10.1080/10556780310001634082. Google Scholar
[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. doi: 10.1023/A:1026094110647. Google Scholar
[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. doi: 10.1360/04ys0167. Google Scholar
[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. doi: 10.1007/s11425-007-0080-x. Google Scholar
[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. doi: 10.1007/s10878-012-9526-3. Google Scholar
[38]	Y. Ye, A.699-approximation algorithm for max-bisection,, Math. Program. Ser. A, 90 (2001), 101. doi: 10.1007/PL00011415. Google Scholar
[39]	Y. Ye and J. Zhang, Approximation of dense-$\fracn{2}$-subgraph and the complement of min-bisection,, J. Global Optim., 25 (2003), 55. doi: 10.1023/A:1021390231133. Google Scholar
[40]	J. Zhang, Y. Ye and Q. Han, Improved approximations for max set splitting and max NAE SAT,, Discrete Appl. Math., 142 (2004), 133. doi: 10.1016/j.dam.2002.07.001. Google Scholar

show all references

References:

[1]	A. Amiri, Customer-oriented catalog segmentation: Effective solution approaches,, Decision Support Syst., 42 (2006), 1860. doi: 10.1016/j.dss.2006.04.010. Google Scholar
[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. doi: 10.1145/1007352.1007355. Google Scholar
[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. doi: 10.1145/1250790.1250818. Google Scholar
[4]	B. Barak, P. Raghavendra and D. Steurer, Rounding semidefinite programming hierarchies via global correlation,, FOCS, (2011), 472. doi: 10.1109/FOCS.2011.95. Google Scholar
[5]	D. Bertsimas and Y. Ye, Semidenite relaxations, multivariate normal distributions, and order statistics,, Handbook of Combinatorial Optimization, 3 (1998), 1. doi: 10.1016/S1386-4181(97)00012-8. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[9]	U. Feige and M. Langberg, Approximation algorithms for maximization problems in graph partitioning,, J. Algorithm, 41 (2001), 174. doi: 10.1006/jagm.2001.1183. Google Scholar
[10]	U. Feige, Relations between average case complexity and approximation complexity,, in Proceedings on 34th Annual ACM Symposium on Theory and Computing, (2002), 534. doi: 10.1145/509907.509985. Google Scholar
[11]	U. Feige and M. Langberg, The $RPR^2$ rounding technique for semidefinite programs,, J. Algorithm, 60 (2006), 1. doi: 10.1016/j.jalgor.2004.11.003. Google Scholar
[12]	A. Frieze and M. Jerrum, Improved approximation algorithms for max $k$-cut and max bisection,, Algorithmica, 18 (1997), 67. doi: 10.1007/BF02523688. Google Scholar
[13]	G. Galbiati and F. Maffioli, Approximation algorithms for maximum cut with limited unbalance,, Theor. Comput. Sci., 385 (2007), 78. doi: 10.1016/j.tcs.2007.05.036. Google Scholar
[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. doi: 10.1145/227683.227684. Google Scholar
[15]	V. Guruswami and A. Sinop, Lasserre hierarchy, higher eigenvalues, and approximation schemes for quadratic integer programming with psd objectives,, FOCS, (2011), 482. doi: 10.1109/FOCS.2011.36. Google Scholar
[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. doi: 10.1002/rsa.10035. Google Scholar
[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. doi: 10.1007/s101070100288. Google Scholar
[18]	Q. Han, Y. Ye, H. Zhang and J. Zhang, On approximation of max-vertex-cover,, Eur. J. Oper. Res., 143 (2002), 342. doi: 10.1016/S0377-2217(02)00330-2. Google Scholar
[19]	C. Helmberg, Cutting Planes Algorithm for Large Scale Semidefinite Relaxations,, ZIB-Report ZR 01-26, (2001), 01. Google Scholar
[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. Google Scholar
[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. doi: 10.1137/S0097539705447372. Google Scholar
[22]	J. Kleinberg, C. Papadimitriou and P. Raghavan, A microeconomic view of data mining,, Data Mining and Knowledge Discovery, 2 (1998), 311. Google Scholar
[23]	J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems,, J. ACM, 51 (2004), 263. doi: 10.1145/972639.972644. Google Scholar
[24]	J. Löfberg, YALMIP: A toolbox for modelling and optimization in matlab,, in Proceedings of the CACSD Conference, (2004). Google Scholar
[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. doi: 10.1137/050642691. Google Scholar
[26]	P. Raghavendra, Optimal algorithms and inapproximability results for every csp,, in Proceedings of the 40th ACM Symposium on Theory of Computing, (2008), 245. doi: 10.1145/1374376.1374414. Google Scholar
[27]	P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, SODA, (2012), 373. Google Scholar
[28]	F. Roupin, From linear to semidefinite programming: An algorithm to obtain semidefinite relaxations for bivalent quadratic problems,, J. Comb. Optim., 8 (2004), 469. doi: 10.1007/s10878-004-4838-6. Google Scholar
[29]	R. Saket, Quasi-Random PCP and hardness of $2$-catalog segmentation,, Foundations of Software Technology and Theoretical Computer Science-FSTTCS, 8 (2010), 447. Google Scholar
[30]	L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. doi: 10.1137/1038003. Google Scholar
[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. Google Scholar
[32]	D. Xu, Y. Ye and J Zhang, A note on approximating the 2-catalog segmentation problem,, Working Paper, (5224). Google Scholar
[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. doi: 10.1080/10556780310001634082. Google Scholar
[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. doi: 10.1023/A:1026094110647. Google Scholar
[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. doi: 10.1360/04ys0167. Google Scholar
[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. doi: 10.1007/s11425-007-0080-x. Google Scholar
[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. doi: 10.1007/s10878-012-9526-3. Google Scholar
[38]	Y. Ye, A.699-approximation algorithm for max-bisection,, Math. Program. Ser. A, 90 (2001), 101. doi: 10.1007/PL00011415. Google Scholar
[39]	Y. Ye and J. Zhang, Approximation of dense-$\fracn{2}$-subgraph and the complement of min-bisection,, J. Global Optim., 25 (2003), 55. doi: 10.1023/A:1021390231133. Google Scholar
[40]	J. Zhang, Y. Ye and Q. Han, Improved approximations for max set splitting and max NAE SAT,, Discrete Appl. Math., 142 (2004), 133. doi: 10.1016/j.dam.2002.07.001. Google Scholar

[1]	J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[2]	Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[3]	Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[4]	Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[5]	Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

2019 Impact Factor: 1.366

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors