-
Previous Article
Optimal assignment of principalship and residual distribution for cooperative R&D
- JIMO Home
- This Issue
-
Next Article
A tropical cyclone-based 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 catalog-segmentation problem,, Unpublished manuscript, (2001). Google Scholar |
[2] |
Y. Doids, V. Guruswami and S. Khanna, The $2$-catalog segmentation problem,, in, (1999), 897. Google Scholar |
[3] |
U. Feige and M. Langberg, The RPR$^2$ rounding technique for semidefinte programs,, Journal of Algorithms, 60 (2006), 1.
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), 67.
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), 1115.
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), 382.
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), 509.
doi: 10.1007/s101070100288. |
[8] |
J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems,, Journal of the ACM, 51 (2004), 263.
doi: 10.1145/972639.972644. |
[9] |
D. Xu and J. Han, Approximation algorithm for max-bisection problem with the positive semidefinite relaxation,, Journal of Computational Mathematics, 21 (2003), 357.
|
[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 } $-DENSE-SUBGRAPH,, Journal of Global Optimization, 27 (2003), 399.
doi: 10.1023/A:1026094110647. |
[11] |
D. Xu, Y. Ye and J. Zhang, A note on approximating the $2$-catalog segmentation problem,, Working Paper, (5224). Google Scholar |
[12] |
D. Xu, Y. Ye and J. Zhang, Approximating the $2$-catalog segmentation problem using semidefinite programming relaxations,, Optimization Methods and Software, 18 (2003), 705.
|
[13] |
Y. Ye, A $.699$-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101.
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, (1999), 679.
|
show all references
References:
[1] |
V. Asodi and S. Safra, On the complexity of the catalog-segmentation problem,, Unpublished manuscript, (2001). Google Scholar |
[2] |
Y. Doids, V. Guruswami and S. Khanna, The $2$-catalog segmentation problem,, in, (1999), 897. Google Scholar |
[3] |
U. Feige and M. Langberg, The RPR$^2$ rounding technique for semidefinte programs,, Journal of Algorithms, 60 (2006), 1.
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), 67.
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), 1115.
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), 382.
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), 509.
doi: 10.1007/s101070100288. |
[8] |
J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems,, Journal of the ACM, 51 (2004), 263.
doi: 10.1145/972639.972644. |
[9] |
D. Xu and J. Han, Approximation algorithm for max-bisection problem with the positive semidefinite relaxation,, Journal of Computational Mathematics, 21 (2003), 357.
|
[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 } $-DENSE-SUBGRAPH,, Journal of Global Optimization, 27 (2003), 399.
doi: 10.1023/A:1026094110647. |
[11] |
D. Xu, Y. Ye and J. Zhang, A note on approximating the $2$-catalog segmentation problem,, Working Paper, (5224). Google Scholar |
[12] |
D. Xu, Y. Ye and J. Zhang, Approximating the $2$-catalog segmentation problem using semidefinite programming relaxations,, Optimization Methods and Software, 18 (2003), 705.
|
[13] |
Y. Ye, A $.699$-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101.
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, (1999), 679.
|
[1] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
[2] |
Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. Semi-automatic segmentation of NATURA 2000 habitats in Sentinel-2 satellite images by evolving open curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1033-1046. doi: 10.3934/dcdss.2020231 |
[3] |
Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. An automated segmentation of NATURA 2000 habitats from Sentinel-2 optical data. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1017-1032. doi: 10.3934/dcdss.2020348 |
[4] |
Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020162 |
[5] |
Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 |
[6] |
Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 |
[7] |
Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020 doi: 10.3934/nhm.2020031 |
[8] |
Xiaoli Lu, Pengzhan Huang, Yinnian He. Fully discrete finite element approximation of the 2D/3D unsteady incompressible magnetohydrodynamic-Voigt regularization flows. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 815-845. doi: 10.3934/dcdsb.2020143 |
[9] |
Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134 |
[10] |
Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020389 |
[11] |
Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 |
[12] |
Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048 |
[13] |
Balázs Kósa, Karol Mikula, Markjoe Olunna Uba, Antonia Weberling, Neophytos Christodoulou, Magdalena Zernicka-Goetz. 3D image segmentation supported by a point cloud. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 971-985. doi: 10.3934/dcdss.2020351 |
[14] |
Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1123-1132. doi: 10.3934/dcdss.2020389 |
[15] |
Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 |
[16] |
Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020463 |
[17] |
Bilal Al Taki, Khawla Msheik, Jacques Sainte-Marie. On the rigid-lid approximation of shallow water Bingham. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 875-905. doi: 10.3934/dcdsb.2020146 |
[18] |
P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178 |
[19] |
Simone Fagioli, Emanuela Radici. Opinion formation systems via deterministic particles approximation. Kinetic & Related Models, 2021, 14 (1) : 45-76. doi: 10.3934/krm.2020048 |
[20] |
Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020054 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]