-
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.
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.
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.
doi: 10.1145/1250790.1250818. |
[4] |
B. Barak, P. Raghavendra and D. Steurer, Rounding semidefinite programming hierarchies via global correlation,, FOCS, (2011), 472.
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.
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. 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. |
[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. |
[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. |
[12] |
A. Frieze and M. Jerrum, Improved approximation algorithms for max $k$-cut and max bisection,, Algorithmica, 18 (1997), 67.
doi: 10.1007/BF02523688. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[27] |
P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, SODA, (2012), 373.
|
[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. |
[29] |
R. Saket, Quasi-Random PCP and hardness of $2$-catalog segmentation,, Foundations of Software Technology and Theoretical Computer Science-FSTTCS, 8 (2010), 447.
|
[30] |
L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49.
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.
|
[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. |
[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. |
[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. |
[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. |
[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. |
[38] |
Y. Ye, A.699-approximation algorithm for max-bisection,, Math. Program. Ser. A, 90 (2001), 101.
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.
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.
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.
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.
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.
doi: 10.1145/1250790.1250818. |
[4] |
B. Barak, P. Raghavendra and D. Steurer, Rounding semidefinite programming hierarchies via global correlation,, FOCS, (2011), 472.
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.
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. 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. |
[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. |
[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. |
[12] |
A. Frieze and M. Jerrum, Improved approximation algorithms for max $k$-cut and max bisection,, Algorithmica, 18 (1997), 67.
doi: 10.1007/BF02523688. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[27] |
P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, SODA, (2012), 373.
|
[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. |
[29] |
R. Saket, Quasi-Random PCP and hardness of $2$-catalog segmentation,, Foundations of Software Technology and Theoretical Computer Science-FSTTCS, 8 (2010), 447.
|
[30] |
L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49.
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.
|
[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. |
[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. |
[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. |
[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. |
[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. |
[38] |
Y. Ye, A.699-approximation algorithm for max-bisection,, Math. Program. Ser. A, 90 (2001), 101.
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.
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.
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 & 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 & 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 & Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062 |
[4] |
Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019044 |
[5] |
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 & Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117 |
[6] |
Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & 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 & Imaging, 2013, 7 (3) : 1099-1113. doi: 10.3934/ipi.2013.7.1099 |
[8] |
Jean-François Babadjian, Clément Mifsud, Nicolas Seguin. Relaxation approximation of Friedrichs' systems under convex constraints. Networks & Heterogeneous Media, 2016, 11 (2) : 223-237. doi: 10.3934/nhm.2016.11.223 |
[9] |
Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015 |
[10] |
Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems & Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645 |
[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 & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030 |
[12] |
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 |
[13] |
Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71 |
[14] |
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 |
[15] |
Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645 |
[16] |
Bertrand Lods, Clément Mouhot, Giuseppe Toscani. Relaxation rate, diffusion approximation and Fick's law for inelastic scattering Boltzmann models. Kinetic & Related Models, 2008, 1 (2) : 223-248. doi: 10.3934/krm.2008.1.223 |
[17] |
Marcel Braukhoff. Global analytic solutions of the semiconductor Boltzmann-Dirac-Benney equation with relaxation time approximation. Kinetic & Related Models, 2020, 13 (1) : 187-210. doi: 10.3934/krm.2020007 |
[18] |
David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429 |
[19] |
Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651 |
[20] |
Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 |
2018 Impact Factor: 1.025
Tools
Metrics
Other articles
by authors
[Back to Top]