A polynomial algorithm for some instances of NP-complete problems

Marius Costandin, Bogdan Gavrea

Abstract


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 problem 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. This is a condition that the given reference point and search set have to meet. However, 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 problem without restrictions on the given reference point and search set is undecided so far. 


Keywords


feasibility criteria and convex optimization and non-convex optimization and quadratic programming.

Full Text:

PDF

References


H. Bauschke, J. M. Borwein On Projection Algorithms for Solving Convex Feasibility Problems SIAM Review, 38(3), 1996.

Robert G. Bland, Donald Goldfarb and Michael J. Todd The Ellipsoid Method: A Survey Cornell University, Ithaca, New York, 1981

S. Boyd, L. Vandenberghe Convex Optimization, Cambridge University Press, ISBN 978-0-521-83378-3, retrieved October 15, (2011)

S. Boyd Subgradient Methods Notes for EE364b, Stanford University, Spring 2013{14

S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan Linear Matrix Inequalities in System and Control Theory Society for Industrial and Applied Mathematics, 1994

C.A. Floudas and V. Visweswaran Quadratic optimization In: Handbook of global optimization, pp. 217-269. Springer, 1995

N. Parikh and S. Boyd Proximal algorithms Foundations and Trends in Optimization 1 123{231, 2013

B. T. Polyak Minimization Of Unsmooth Functionals Moscow 1968

B. T Polyak A general method for solving extremal problems. DokE. Akad. Nauk SSSR. 174, 1, 33-36, 1967.

B.T. Polyak Introduction to Optimization Optimization Software New York

Sahni, Sartaj Computationally Related Problems SIAM J Comput, vol. 3, nr. 4, 1974

H. H. Bauschke1, M. N. Dao, D. Noll, H. M. Phan 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

C. A. De Bernardi, E. Miglierina, E. Molho Stability of a convex feasibility problem Journal of Global Optimization, https://doi.org/10.1007/s10898-019-00806-w, 2019

A. Beck 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 (2007) 39:113{126 DOI 10.1007/s10898-006-9127-8

A. Beck, D. Pan A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints J Glob Optim DOI 10.1007/s10898-017-0521-1, 2017

P. L. DE Angelis, I. M. Bomze and G. Toraldo Ellipsoidal Approach to Box-Constrained Quadratic Problems Journal of Global Optimization 28: 1{15, 2004, 2004 Kluwer Academic Publishers. Printed in the Netherlands

D. Y. Gao, N. Ruan Solutions to quadratic minimization problems with box and integer constraints J Glob Optim (2010) 47:463{484, DOI10.1007/s10898-009-9469-0

L. T. H. AN and P. D. TAO A Branch and Bound Method via d.c. Optimization Algorithms and Ellipsoidal Technique for Box Constrained Nonconvex Quadratic Problems Journal of Global Optimization 13: 171{206, 1998, 1998 Kluwer Academic Publishers. Printed in the Netherlands.

Boroczky K., Wintsche G. Covering the Sphere by Equal Spherical

Balls Discrete and Computational Geometry. Algorithms and Combinatorics, vol 25. Springer, Berlin, Heidelberg., https://doi.org/10.1007/978-3-642-55566-4_10, 2003

Boroczky K., Wintsche G. Approximation algorithms for indefinite quadratic programming Mathematical Programming 57 (1992) 279-311, North-Holland




DOI: http://dx.doi.org/10.24193/subbmath.2024.1.15

Refbacks

  • There are currently no refbacks.