# Tag Info

2

If the trajectories must be lines and $\epsilon$ is small enough, the problem can be solved with min-cost matching. If all coordinates are integers with absolute value bounded by $H$, then two disjoint intervals with integer endpoints have distance at least $\frac{1}{4H}$ from each other. Hence if $\epsilon$ is less than this value, it might as well be 0. ...

2

If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern variants. Then: Define a distance function that gives the closest BB to the BB of your search-object. Find the BB in the index that is closest to the BB of you ...

2

Yes, this is NP-hard. Since neither the $a_i$ nor the $d_i$ depend on the solution, the problem is equivalent to the problem of minimizing the sum of the completion times of the requests, which is known in the scheduling literature as "$1|r_i|\sum C_i$" and is NP-hard. Reference: J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine ...

1

One approach is to solve the system without this preference constraint and find the wastage. Suppose you can achieve wastage 1100. Then, add a new constraint that the wastage cannot exceed 1100, and modify the objective function to slightly penalize use of the back components, and solve that modified problem.

1

The best I can come up with is to compute the centroid of each object and store the centroids in a nearest-neighbor data structure; to find the matches for a test object $T$, look up its centroid in the data structure and iterate through the objects in order of the distance between their centroid and $T$'s centroid and compute the distance to each. The ...

1

In general, we definitely don't know this. In fact, it's practically always so that a-priori, we don't know how well a particular metaheuristic performs (let alone proving optimality) on a given instance (or family of instances) until we try. It should also be noted that we usually go for metaheuristics only when the problem is so hard it seems unlikely it ...

1

An answer to this precise question is given by Bellare and Goldwasser, "The Complexity of Decision Versus Search", SIAM Journal on Computing, 23:1 (February 1994), DOI /10.1137/S0097539792228289; a more expository version of the above is Bellare's class note on this. The short answer is that if the decision problem is NP-complete, the search problem is "NP-...

Only top voted, non community-wiki answers of a minimum length are eligible