
Previous Article
Optimal assignment of principalship and residual distribution for cooperative R&D
 JIMO Home
 This Issue

Next Article
A tropical cyclonebased method for global optimization
An improved approximation algorithm for the $2$catalog segmentation problem using semidefinite programming relaxation
1.  College of Science, Tianjin University of Technology, Tianjin 300384, China 
2.  Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124, China, China 
References:
[1] 
V. Asodi and S. Safra, On the complexity of the catalogsegmentation problem, Unpublished manuscript, 2001. 
[2] 
Y. Doids, V. Guruswami and S. Khanna, The $2$catalog segmentation problem, in "Proceedings of SODA'' (Maryland, Baltimore), 1999, pp. 897898. 
[3] 
U. Feige and M. Langberg, The RPR$^2$ rounding technique for semidefinte programs, Journal of Algorithms, 60 (2006), 123. doi: 10.1016/j.jalgor.2004.11.003. 
[4] 
A. Frieze and M. Jerrum, Improved approximation algorithms for MAX $k$CUT and MAX BISECTION, Algorithmica, 18 (1997), 6781. doi: 10.1007/BF02523688. 
[5] 
M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995), 11151145. doi: 10.1145/227683.227684. 
[6] 
E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Structures & Algorithms, 20 (2002), 382402. doi: 10.1002/rsa.10035. 
[7] 
Q. Han, Y. Ye and J. Zhang, An improved rounding method and semidefinite programming relaxation for graph partition, Mathematical Programming, 92 (2002), 509535. doi: 10.1007/s101070100288. 
[8] 
J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems, Journal of the ACM, 51 (2004), 263280. doi: 10.1145/972639.972644. 
[9] 
D. Xu and J. Han, Approximation algorithm for maxbisection problem with the positive semidefinite relaxation, Journal of Computational Mathematics, 21 (2003), 357366. 
[10] 
D. Xu, J. Han, Z. Huang and L. Zhang, Improved approximation algorithms for MAX$ \frac{ n }{ 2 } $DIRECTED BISECTION and MAX$ \frac{ n }{ 2 } $DENSESUBGRAPH, Journal of Global Optimization, 27 (2003), 399410. doi: 10.1023/A:1026094110647. 
[11] 
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, 2002. 
[12] 
D. Xu, Y. Ye and J. Zhang, Approximating the $2$catalog segmentation problem using semidefinite programming relaxations, Optimization Methods and Software, 18 (2003), 705719. 
[13] 
Y. Ye, A $.699$approximation algorithm for MaxBisection, Mathematical Programming, 90 (2001), 101111. doi: 10.1007/PL00011415. 
[14] 
U. Zwick, Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, in "Proceedings of STOC'' (Atlanta, GA), 1999, pp. 679687. 
show all references
References:
[1] 
V. Asodi and S. Safra, On the complexity of the catalogsegmentation problem, Unpublished manuscript, 2001. 
[2] 
Y. Doids, V. Guruswami and S. Khanna, The $2$catalog segmentation problem, in "Proceedings of SODA'' (Maryland, Baltimore), 1999, pp. 897898. 
[3] 
U. Feige and M. Langberg, The RPR$^2$ rounding technique for semidefinte programs, Journal of Algorithms, 60 (2006), 123. doi: 10.1016/j.jalgor.2004.11.003. 
[4] 
A. Frieze and M. Jerrum, Improved approximation algorithms for MAX $k$CUT and MAX BISECTION, Algorithmica, 18 (1997), 6781. doi: 10.1007/BF02523688. 
[5] 
M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995), 11151145. doi: 10.1145/227683.227684. 
[6] 
E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Structures & Algorithms, 20 (2002), 382402. doi: 10.1002/rsa.10035. 
[7] 
Q. Han, Y. Ye and J. Zhang, An improved rounding method and semidefinite programming relaxation for graph partition, Mathematical Programming, 92 (2002), 509535. doi: 10.1007/s101070100288. 
[8] 
J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems, Journal of the ACM, 51 (2004), 263280. doi: 10.1145/972639.972644. 
[9] 
D. Xu and J. Han, Approximation algorithm for maxbisection problem with the positive semidefinite relaxation, Journal of Computational Mathematics, 21 (2003), 357366. 
[10] 
D. Xu, J. Han, Z. Huang and L. Zhang, Improved approximation algorithms for MAX$ \frac{ n }{ 2 } $DIRECTED BISECTION and MAX$ \frac{ n }{ 2 } $DENSESUBGRAPH, Journal of Global Optimization, 27 (2003), 399410. doi: 10.1023/A:1026094110647. 
[11] 
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, 2002. 
[12] 
D. Xu, Y. Ye and J. Zhang, Approximating the $2$catalog segmentation problem using semidefinite programming relaxations, Optimization Methods and Software, 18 (2003), 705719. 
[13] 
Y. Ye, A $.699$approximation algorithm for MaxBisection, Mathematical Programming, 90 (2001), 101111. doi: 10.1007/PL00011415. 
[14] 
U. Zwick, Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, in "Proceedings of STOC'' (Atlanta, GA), 1999, pp. 679687. 
[1] 
Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881893. doi: 10.3934/jimo.2010.6.881 
[2] 
Chengjin Li. Parameterrelated projectionbased iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 511520. doi: 10.3934/naco.2020048 
[3] 
Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial and Management Optimization, 2020, 16 (3) : 15271538. doi: 10.3934/jimo.2019015 
[4] 
Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613630. doi: 10.3934/amc.2020034 
[5] 
Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial and Management Optimization, 2016, 12 (4) : 11871197. doi: 10.3934/jimo.2016.12.1187 
[6] 
Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127145. doi: 10.3934/amc.2013.7.127 
[7] 
Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193206. doi: 10.3934/naco.2012.2.193 
[8] 
Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521529. doi: 10.3934/jimo.2012.8.521 
[9] 
Cristian Dobre. Mathematical properties of the regular *representation of matrix $*$algebras with applications to semidefinite programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 367378. doi: 10.3934/naco.2013.3.367 
[10] 
Behrouz Kheirfam, Morteza Moslemi. On the extension of an arcsearch interiorpoint algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261275. doi: 10.3934/naco.2018015 
[11] 
Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial and Management Optimization, 2019, 15 (2) : 893908. doi: 10.3934/jimo.2018076 
[12] 
Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $means problem with penalty. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021067 
[13] 
Jian Sun, Haiyun Sheng, Yuefang Sun, Donglei Du, Xiaoyan Zhang. Approximation algorithm with constant ratio for stochastic prizecollecting Steiner tree problem. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021116 
[14] 
Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $means problem^{†}. Journal of Industrial and Management Optimization, 2022, 18 (1) : 411426. doi: 10.3934/jimo.2020160 
[15] 
Shi Yan, Jun Liu, Haiyang Huang, XueCheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems and Imaging, 2019, 13 (3) : 653677. doi: 10.3934/ipi.2019030 
[16] 
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) : 645657. doi: 10.3934/ipi.2011.5.645 
[17] 
Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 6581. doi: 10.3934/jimo.2015.11.65 
[18] 
Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on LogSigmoid function for nonconvex semidefinite programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 651669. doi: 10.3934/jimo.2009.5.651 
[19] 
Thierry Horsin, Peter I. Kogut, Olivier Wilk. Optimal $L^2$control problem in coefficients for a linear elliptic equation. II. Approximation of solutions and optimality conditions. Mathematical Control and Related Fields, 2016, 6 (4) : 595628. doi: 10.3934/mcrf.2016017 
[20] 
Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial and Management Optimization, 2017, 13 (2) : 10091024. doi: 10.3934/jimo.2016059 
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]