Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum distance between all pairs of points is maximized?

Assume that the intervals are bounded by a positive integer $C$.

What's the complexity of this problem?

If the intervals are non-overlapping, I know how to solve this with linear programming (indeed, using a system of difference constraints and Bellman-Ford), but what can we say about the general case where intervals might overlap?

Note: Most comments/answers so far are looking for a polynomial solution. Note that it is possible that this problem is NP-complete. I know that it was the style of this teacher to include problems for which students had to prove NP-completeness.

  • 2
    $\begingroup$ What are your thoughts on the subject? $\endgroup$ – Yuval Filmus Dec 15 '14 at 23:00
  • $\begingroup$ @YuvalFilmus I have came back to this problem over a couple of months, but I haven't figured it out yet. No valuable ideas so far... $\endgroup$ – becko Dec 16 '14 at 13:07
  • $\begingroup$ 1. You mention this was assigned on an exam. What was the course? What subjects were taught in the course? In other words, what topics could people taking the exam have been expected to know? Was it an undergraduate algorithms course? A graduate course? 2. Are the points $P_1,\dots,P_n$ required to be integers, or can they be real numbers? $\endgroup$ – D.W. Dec 18 '14 at 21:26
  • $\begingroup$ @D.W. The points can be real numbers, but if restricting $P_i$ to the integers makes a difference, I would like to know the solution in that case as well. The course was on algorithms and complexity. I attended it but did not do the exam myself since it did not give me credits. Topics covered included recurrence, greedy algorithms, some NP-complete problems (knapsack problem and finding Hamilton cycle come to mind), proving NP-completeness, etc. $\endgroup$ – becko Dec 18 '14 at 21:35
  • $\begingroup$ I don't remember all the topics in the course, but I'm not taking the course anymore, so don't mind if you solve the problem using something you find on any book/paper! If you point me to the reference I'll read it. $\endgroup$ – becko Dec 18 '14 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.