Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I don't think this is NP-complete, because I think we can find and recognize a solution with at most O(n^2m^2) guesses.</p> <p>So as not to worry about ties, go from integers to reals and add a very small amount of jitter. I think of this as random, but I think you could chose deterministic jitter to achieve the same effect.</p> <p>Think of the problem as that of choosing from a collection of coloured points laid out on the real line so as to pick one point of each colour and minimise the sum of absolute differences between them.</p> <p>I consider only the case when n is even. The median of the set of solution points occurs between the two central points. For each point in the solution set, there is no point of the same colour between it and the two centre points (or we could improve the solution). For the same reason, each point is the closest point of that colour to the median of the n-1 points we get if we remove it from the solution set.</p> <p>Using our (nm)^2 guesses we guess the identity of the two central points in the solution set. This leaves us n-2 points to find, and we can reduce the possibilities to two of each colour, the closest point to the two central points on each side of those two points.</p> <p>Now consider the median formed by removing one point from the solution set. If the point we remove is on the right side of the two central points, the median is the left of those two points. If the point we remove is on the left side, the median is the right of those two points. In a solution set, the point we have just removed is closer to the new median than any other point of that colour, and that new median is the further of the two central points from it. So we can distinguish it from the other candidate of the same colour - it is whichever of the two is closest to the further of the two central points.</p> <p>Therefore by making at most O(n^2*m^2) guesses we can find a possible solution set for each get, and from these solution sets we choose the one with smallest objective to get the global minimum. Each guess takes some work - maybe O(m) so this may well be an O(n^2m^3) with a completely naive implementation - perhaps mostly a theoretical approach.</p> <p>Perhaps this is too good to be true, but can we turn this into a proof of simply checking each point in the data together with the point of each other colour closest to it? An argument would be that if we have two points and we can recognize each point in the solution as closest to the furthest of the two points then this point must also be closest to the other point in the pair. So guessing either point in the pair and finding the closest points to it might work. This begins to look a lot like a proof of Evgeny Kluev's solution</p>
    singulars
    1. This table or related slice is empty.
    1. POSelecting an integer from each of the given n sets of integers such that the sum of their pairwise distances is minimized
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USmcdowella
    1. USmcdowella
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks. Checking it out now. I agree with the O(n^2m^2 part). I am working on understanding your solution. But, I am happy because I have another solution which seems like O(n^2m^2) too. I will add it as an edit.
      singulars
      1. PO
      1. USuser1669710
    2. COmine turned out O(nm^3), but may be I am wrong. still working out your soln.
      singulars
      1. PO
      1. USuser1669710
    3. COI haven't really considered the order except to show it is polynomial. I have counted guesses and each guess takes perhaps O(m) work but I haven't considered more efficient ways of implementing it. Perhaps it is too good to be true but I have edited my answer to suggest that you might just need to guess one point, in which case it looks a lot like Evgeny Kluev's solution - try each point together with one point of each other colour closest to it as a possible solution.
      singulars
      1. PO
      1. USmcdowella
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload