Approximation Algorithms for Discrete Polynomial Optimization
Tóm tắt
In this paper, we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete (typically binary) variables. Such models have natural applications in graph theory, neural networks, error-correcting codes, among many others. In particular, we focus on three types of optimization models: (1) maximizing a homogeneous polynomial function in binary variables; (2) maximizing a homogeneous polynomial function in binary variables, mixed with variables under spherical constraints; (3) maximizing an inhomogeneous polynomial function in binary variables. We propose polynomial-time randomized approximation algorithms for such polynomial optimization models, and establish the approximation ratios (or relative approximation ratios whenever appropriate) for the proposed algorithms. Some examples of applications for these models and algorithms are discussed as well.
Tài liệu tham khảo
Aardal, K., Hurkens, C.A.J., Lenstra, A.K.: Solving a system of linear Diophantine equations with lower and upper bounds on the variables. Math. Oper. Res. 25, 427–442 (2000)
Alon, N., Naor, A.: Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput. 35, 787–803 (2006)
Alon, N., de la Vega, W.F., Kannan, R., Karpinski, M.: Random sampling and approximation of MAX-CSP problems. In: Proceedings of the 34th Annuals ACM Symposium on Theory of Computing, pp. 232–239 (2002)
Ansari, N., Hou, E.: Computational Intelligence for Optimization. Kluwer Academic, Norwell (1997)
Balinski, M.L.: On a selection problem. Manag. Sci. 17, 230–231 (1970)
Beihoffer, D., Hendry, J., Nijenhuis, A., Wagon, S.: Faster algorithms for Frobenius numbers. Electron. J. Comb. 12, R27 (2005)
Bertsimas, D., Ye, Y.: Semidefinite relaxations, multivariate normal distributions, and order statistics. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 3, pp. 1–19. Kluwer Academic, Norwell (1998)
Bruck, J., Blaum, M.: Neural networks, error-correcting codes, and polynomials over the binary n-cube. IEEE Trans. Inf. Theory 35, 976–987 (1989)
Charikar, M., Wirth, A.: Maximizing quadratic programs: extending Grothendieck’s inequality. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 54–60 (2004)
Chen, B., He, S., Li, Z., Zhang, S.: Maximum block improvement and polynomial optimization. SIAM J. Optim. 22, 87–107 (2012)
Cornuéjols, G., Dawande, M.: A class of hard small 0–1 programs, integer programming and combinatorial optimization. Lect. Notes Comput. Sci. 1412, 284–293 (1998)
Feige, U., Ofek, E.: Easily refutable subformulas of large random 3CNF formulas. In: Automata, Languages and Programming. Lecture Notes in Compuer Science, vol. 3142, pp. 519–530 (2004)
Friedman, J., Goerdt, A., Krivelevich, M.: Recognizing more unsatisfiable random k-SAT instances efficiently. SIAM J. Comput. 35, 408–430 (2005)
Frieze, A.M., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19, 175–200 (1999)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)
Hammer, P.L., Rudeanu, S.: Boolean Methods in Operations Research. Springer, New York (1968)
Hansen, P.: Methods of nonlinear 0–1 programming. Ann. Discrete Math. 5, 53–70 (1979)
He, S., Li, Z., Zhang, S.: Approximation algorithms for homogeneous polynomial optimization with quadratic constraints. Math. Program. 125, 353–383 (2010)
He, S., Li, Z., Zhang, S.: General constrained polynomial optimization: an approximation approach. Technical report, Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong (2009)
Hopfield, J.J., Tank, D.W.: “Neural” computation of decisions in optimization problem. Biol. Cybern. 52, 141–152 (1985)
Huang, Y., Zhang, S.: Approximation algorithms for indefinite complex quadratic maximization problems. Sci. China Math. 53, 2697–2708 (2010)
Kannan, R.: Spectral methods for matrices and tensors. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pp. 1–12 (2010)
Khot, S., Naor, A.: Linear equations modulo 2 and the L 1 diameter of convex bodies. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 318–328 (2007)
Kofidis, E., Regalia, Ph.: On the best rank-1 approximation of higher order supersymmetric tensors. SIAM J. Matrix Anal. Appl. 23, 863–884 (2002)
Li, Z.: Polynomial optimization problems—approximation algorithms and applications. Ph.D. thesis, The Chinese University of Hong Kong, Shatin, Hong Kong (2011)
Nesterov, Yu.: Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 9, 141–160 (1998)
Nesterov, Yu.: Random walk in a simplex and quadratic optimization over convex polytopes. CORE discussion paper, UCL, Louvain-la-Neuve, Belgium (2003)
Purser, M.: Introduction to Error-Correcting Codes. Artech House, Norwood (1995)
Rhys, J.M.W.: A selection problem of shared fixed costs and network flows. Manag. Sci. 17, 200–207 (1970)
So, A.M.-C.: Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems. Math. Program. 129, 357–382 (2011)