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– Yuval Filmus2014年12月15日 23:00:56 +00:00Commented 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– a06e2014年12月16日 13:07:17 +00:00Commented 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.– D.W. ♦2014年12月18日 21:26:22 +00:00Commented 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– a06e2014年12月18日 21:35:15 +00:00Commented 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– a06e2014年12月18日 21:36:04 +00:00Commented Dec 18, 2014 at 21:36