Is time complexity of an SOCP formulation always polynomial?
May there be some situations such that time to solve an SOCP is not polynomial? For example,just an example, when strong duality does not hold, SOCP cannot be solved in polynomial time. Can we say such things?
These questions come to my mind because of the Fermat-Weber problem (problem of locating a single facility to serve “n” customers so as to minimize weighted sum of euclidean distances between the facility and the customers). In the literature, there is not any polynomial algorithm to solve this problem. Weiszfeld algorithm that is the most famous algorithm to solve Fermat-Weber problem fails to solve problem when the facility location and the location of one of the customers coincide.
I formulated Fermat-Weber problem as an SOCP problem. If every SOCP formulation can be solved in polynomial time, then Fermat-Weber problem is solved in polynomial time! To be able to say that “Fermat-Weber problem can be solved in polynomial time”, I have to find the answers of the questions I asked above.
SOCP solve in polynomial time. How that is done you can see in the reference mentioned at the end.
As far I remember the Fermat-Weber then it is special case of the minimum sum of norm problem i.e. it has the form \min_x \sum_i w_i || x - y_i ||_2.
For positive weights w_i that problem is solvable in polynomial time using SOCP. And this has been known before 2000.
@article{DBLP:journals/mp/AndersenRT03,
author = {Erling D. Andersen and
Cornelis Roos and
Tam{'a}s Terlaky},
title = {On implementing a primal-dual interior-point method for
conic quadratic optimization},
journal = {Math. Program.},
volume = {95},
number = {2},
year = {2003},
pages = {249-277},
ee = {http://dx.doi.org/10.1007/s10107-002-0349-3},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
In the “Handbook of Discrete and Combinatorial Mathematics (Editor: Kenneth H. Rosen,2000)” there is Hakimi’s chapter called as “Location Theory”. Hakimi says that “No polynomial-time algorithm for the Weber Problem, even when p=1, has been discovered.”
Was solving Fermat-Weber problem in polynomial time with SOCP discovered after 2000?
I have clarified my post as to which problem I think it is known to polynomial solvable. Do you have a precise description of the Fermat Weber problem?
The Fermat Weber problem in the chapter written by Hakimi when p=1 corresponds to exactly the problem you have described. I have found another reference which also mentions that the classical Fermat-Weber problem is not known to be either polynomial time solvable or NP-hard.
For instance the algorithm in http://dl.acm.org/citation.cfm?id=589138 can solve the problem shown above. This proves that at least since 1999 it has been know the problem is polynomial solvable.