A polynomial algorithm for some instances of NP-complete problems
DOI:
https://doi.org/10.24193/subbmath.2024.1.15Keywords:
Feasibility criteria, convex optimization, non-convex optimization, quadratic programmingAbstract
In this paper, given a fixed reference point and a fixed intersection of finitely many equal radii balls, we consider the problem of finding a point in the said set which is the most distant, under Euclidean distance, to the said reference point. This proble is NP-complete in the general setting. We give sufficient conditions for the existence of an algorithm of polynomial complexity which can solve the problem, in a particular setting. Our algorithm requires that any point in the said intersection to be no closer to the given reference point than the radius of the intersecting balls. Checking this requirement is a convex optimization problem hence one can decide if running the proposed algorithm enjoys the presented theoretical guarantees. We also consider the problem where a fixed initial reference point and a fixed polytope are given and we want to find the farthest point in the polytope to the given reference point. For this problem we give sufficient conditions in which the solution can be found by solving a linear program. Both these problems are known to be NP-complete in the general setup, i.e. the existence of an algorithm which solves any of the above problems without restrictions on the given reference point and search set is undecided so far.
Mathematics Subject Classification (2010): 90-08.
Received 21 December 2021; Accepted 01 August 2023
References
An, L.T.H., Tao, P.D., A branch and bound method via d.c. optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems, Journal of Global Optimization, 13(1998), 171-206.
Baraczky, K., Wintsche, G., Covering the Sphere by Equal Spherical Balls, Discrete and Computational Geometry, Algorithms and Combinatorics, 25, Springer, Berlin, Heidelberg.
Baraczky, K., Wintsche, G., Approximation algorithms for indefinite quadratic programming, Mathematical Programming, 57(1992) 279-311.
Bauschke, H., Borwein, J.M., On projection algorithms for solving convex feasibility problems, SIAM Review, 38(3), 1996.
Bauschkel, H.H., Dao, M.N., Noll, D., Phan, H.M., On Slater’s condition and finite convergence of the Douglas-Rachford algorithm for solving convex feasibility problems in Euclidean spaces, Journal of Global Optimization., DOI 10.1007/s10898-015-0373-5, 2015.
Beck, A., On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls, J. Glob. Optim., 39(2007), 113-126.
Beck, A., Pan, D., A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, J. Glob. Optim., 2017.
Bland, R.G., Goldfarb, D., Todd, M.J., The Ellipsoid Method: A Survey Cornell University, Ithaca, New York, 1981.
Boyd, S., Subgradient Methods, Notes for EE364b, Stanford University, Spring 2013-14.
Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V., Linear Matrix Inequalities in System and Control Theory Society for Industrial and Applied Mathematics, 1994.
Boyd, S., Vandenberghe, L., Convex Optimization, Cambridge University Press, 2011.
De Angelis, P.L., Bomze, I.M., Toraldo, G., Ellipsoidal Approach to Box-Constrained Quadratic Problems, Journal of Global Optimization, 28(2004), 1-15.
De Bernardi, C.A., Miglierina, E., Molho, E., Stability of a convex feasibility problem, Journal of Global Optimization, 2019.
Floudas, C.A., Visweswaran, V., Quadratic Optimization, In: Handbook of Global Optimization, 217-269. Springer, 1995.
Gao, D.Y., Ruan, N., Solutions to quadratic minimization problems with box and integer constraints, J. Glob. Optim., 47(2010), 463-484.
Parikh, N., Boyd, S., Proximal algorithms, Foundations and Trends in Optimization, 1(2013), 123-231.
Polyak, B.T., A general method for solving extremal problems, Dok. Akad. Nauk SSSR, 174(1967), no. 1, 33-36.
Polyak, B.T., Minimization of Unsmooth Functionals, Moscow, 1968.
Polyak, B.T., Introduction to Optimization, Optimization Software New York.
Sahni, S., Computationally Related Problems, SIAM J. Comput., 3(1974), nr. 4.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Studia Universitatis Babeș-Bolyai Mathematica
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
