-
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
Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix
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 |
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. |
show all references
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. |
[1] |
Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 |
[2] |
Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial and Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076 |
[3] |
Jinling Zhao, Wei Chen, Su Zhang. Immediate schedule adjustment and semidefinite relaxation. Journal of Industrial and Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062 |
[4] |
Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117 |
[5] |
Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044 |
[6] |
Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185 |
[7] |
Ruiliang Zhang, Xavier Bresson, Tony F. Chan, Xue-Cheng Tai. Four color theorem and convex relaxation for image segmentation with any number of regions. Inverse Problems and Imaging, 2013, 7 (3) : 1099-1113. doi: 10.3934/ipi.2013.7.1099 |
[8] |
Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015 |
[9] |
Jean-François Babadjian, Clément Mifsud, Nicolas Seguin. Relaxation approximation of Friedrichs' systems under convex constraints. Networks and Heterogeneous Media, 2016, 11 (2) : 223-237. doi: 10.3934/nhm.2016.11.223 |
[10] |
Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030 |
[11] |
Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems and Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030 |
[12] |
Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems and Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645 |
[13] |
Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete and Continuous Dynamical Systems, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 |
[14] |
Gilles Carbou, Bernard Hanouzet. Relaxation approximation of the Kerr model for the impedance initial-boundary value problem. Conference Publications, 2007, 2007 (Special) : 212-220. doi: 10.3934/proc.2007.2007.212 |
[15] |
Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial and Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71 |
[16] |
Chengjin Li. Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 511-520. doi: 10.3934/naco.2020048 |
[17] |
Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008 |
[18] |
Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645 |
[19] |
Yarui Duan, Pengcheng Wu, Yuying Zhou. Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022017 |
[20] |
Ouafa Belguidoum, Hassina Grar. An improved projection algorithm for variational inequality problem with multivalued mapping. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022002 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]