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$ Dec 15, 2014 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$
    – a06e
    Dec 16, 2014 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, 2014 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$
    – a06e
    Dec 18, 2014 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$
    – a06e
    Dec 18, 2014 at 21:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.