Rezumat articol ediţie STUDIA UNIVERSITATIS BABEŞ-BOLYAI

În partea de jos este prezentat rezumatul articolului selectat. Pentru revenire la cuprinsul ediţiei din care face parte acest articol, se accesează linkul din titlu. Pentru vizualizarea tuturor articolelor din arhivă la care este autor/coautor unul din autorii de mai jos, se accesează linkul din numele autorului.

 
       
         
    STUDIA MATHEMATICA - Ediţia nr.1 din 2024  
         
  Articol:   A POLYNOMIAL ALGORITHM FOR SOME INSTANCES OF NP-COMPLETE PROBLEMS.

Autori:  MARIUS COSTANDIN, BOGDAN GAVREA.
 
       
         
  Rezumat:   DOI: 10.24193/subbmath.2024.1.15

Received 21 December 2021; Accepted 01 August 2023. Published Online: 2024-03-20
Published Print: 2024-03-30
pp. 233-244

VIEW PDF


FULL PDF

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 problem without restrictions on the given reference point and search set is undecided so far.

Mathematics Subject Classification (2010): 90-08.
Keywords: Feasibility criteria, convex optimization, non-convex optimization, quadratic programming.
 
         
     
         
         
      Revenire la pagina precedentă