A method and apparatus for providing a facility location plan for a network with a V-shaped facility cost are disclosed. For example, the method receives an event from a queue, wherein the event comprises an open event or a tight event. The method connects a plurality of adjacent clients to a facility, if the event comprises the open event, and adds a new client-facility edge to a graph comprising a plurality of client-facility edges, if the event comprises the tight event.