Citation: |
[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. |