Approximation Algorithms

There is a one-dimensional garden on the x-axis between coordinates 0 and n. There are n + 1 taps located at integer positions [0, 1, 2, ..., n]; tap i waters area [i - ranges[i], i + ranges[i]]. Return the minimum number of taps that must be opened to water the entire garden, or -1 if it is impossible.

Given an array positions where positions[i] = [xi, yi] are the 2D coordinates of customer locations, return the minimum possible sum of Euclidean distances from a chosen service-center point to all customer locations. Answers within 10^-5 of the actual value are accepted. (This is the geometric-median / Weber problem; solve iteratively, e.g., with Weiszfeld's algorithm or simulated annealing.)