Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix

Fang  Tian; Zi-Long  Liu

doi:10.3934/jimo.2016.12.1249

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

October 2016, 12(4): 1249-1265. doi: 10.3934/jimo.2016.12.1249

Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix

Fang Tian ^1, and Zi-Long Liu ^2,

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

Received December 2013 Revised October 2015 Published January 2016

Abstract
Related Papers

$2$-CatSP is a fundamental NP-Complete optimization problem, which is formulated as given a ground set $U$ of $n$ items, $m$ subsets $S_1,S_2,\cdots,$ $S_m$ of $U$ and an integer $1\leq t\leq n$, find two subsets $A_1$ and $A_2$ of $U$ such that $|A_1|=|A_2|\leq t$ and $\sum_{i=1}^{m}\max\left(|S_i\cap A_1|,|S_i\cap A_2|\right)$ is maximized. In this paper, we reconsider randomized approximation algorithms for $2$-CatSP without and with triangle inequalities in terms of a new positive semidefinite matrix reflecting more information on unbalanced properties. The performance ratios of our algorithm are much better than the current best ones of Xu et al in (Optim. Method. Softw., 18(6): 705-719, 2003) for general cases under unbalanced parameters $\sigma=t/n\geq 0.50$ by our rigorous analysis. In particular, we get 0.6700 and 0.7250 without and with triangle inequalities for the most important subcase $\sigma=0.50$, improving previously best ratios 0.6430 and 0.6736 in corresponding environment. Indeed recently Wu et al (J. Ind. Manag. Optim. 8: 117-126, 2012) and Xu et al in (J. Comb. Optim., 27: 315-327, 2014) also considered approximate strategies for its disjoint subcase $A_1\cap A_2=\emptyset$ as $\sigma=0.50$ with ratios 0.7317 and 0.7469, which can be reduced to max bisection problems of graphs.

Keywords: approximation algorithm, Catalog segmentation, semidefinite relaxation, Lasserres SDP hierarchy., triangle inequality.

Mathematics Subject Classification: Primary: 90C25, 90C27; Secondary: 68Q25, 68W2.

Citation: Fang Tian, Zi-Long Liu. Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1249-1265. doi: 10.3934/jimo.2016.12.1249

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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[4]	B. Barak, P. Raghavendra and D. Steurer, Rounding semidefinite programming hierarchies via global correlation,, FOCS, (2011), 472. doi: 10.1109/FOCS.2011.95. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[12]	A. Frieze and M. Jerrum, Improved approximation algorithms for max $k$-cut and max bisection,, Algorithmica, 18 (1997), 67. doi: 10.1007/BF02523688. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[27]	P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, SODA, (2012), 373. Google Scholar
[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. Google Scholar
[29]	R. Saket, Quasi-Random PCP and hardness of $2$-catalog segmentation,, Foundations of Software Technology and Theoretical Computer Science-FSTTCS, 8 (2010), 447. Google Scholar
[30]	L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. doi: 10.1137/1038003. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[38]	Y. Ye, A.699-approximation algorithm for max-bisection,, Math. Program. Ser. A, 90 (2001), 101. doi: 10.1007/PL00011415. Google Scholar
[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. Google Scholar
[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. Google Scholar

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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[4]	B. Barak, P. Raghavendra and D. Steurer, Rounding semidefinite programming hierarchies via global correlation,, FOCS, (2011), 472. doi: 10.1109/FOCS.2011.95. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[12]	A. Frieze and M. Jerrum, Improved approximation algorithms for max $k$-cut and max bisection,, Algorithmica, 18 (1997), 67. doi: 10.1007/BF02523688. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[27]	P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, SODA, (2012), 373. Google Scholar
[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. Google Scholar
[29]	R. Saket, Quasi-Random PCP and hardness of $2$-catalog segmentation,, Foundations of Software Technology and Theoretical Computer Science-FSTTCS, 8 (2010), 447. Google Scholar
[30]	L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. doi: 10.1137/1038003. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[38]	Y. Ye, A.699-approximation algorithm for max-bisection,, Math. Program. Ser. A, 90 (2001), 101. doi: 10.1007/PL00011415. Google Scholar
[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. Google Scholar
[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. Google Scholar

[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

American Institute of Mathematical Sciences

Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors