This is a problem from computational geometry, with applications in wireless networking.

We are given n links (arcs) in the plane, in arbitrary position, where as each link is defined by a source node and a destination node (in other words, by two points in the plane). These links represent communication requests that must be scheduled in time. In particular, we need an algorithm which assigns a color to each link such that all links with the same color can be scheduled concurrently. The number of used colors should be minimized. Whether a set of links can be scheduled concurrently depends on the so-called signal-to-interference-plus-noise ratio (SINR). This is a standard model in communication engineering. In short, the energy received by the destination of a link (from its corresponding source) should be at least a factor beta higher than the sum of the interfering energies received from competing sources (sources with the same color), where energy drops with distance (received power = sent power * distance^(-alpha) for a parameter alpha). Good values for alpha and beta are alpha = beta = 3. There are two variants of the problem. In one variant the sources all use the same power to transmit (constant power version, CP), in the other variant each source can choose its own transmission power (arbitrary power, AP). There are quite some differences between the two variants.

Questions (for CP or AP, or any other model that seems interesting, e.g. a model without noise):

-          As a starter: Can you give an example of two links that can be scheduled in one time slot with AP but not with CP? (*)

-          How much worse can CP be than AP (asymptotically in n)? (* - **)

-          Show that the problem is NP-complete, or give an optimal algorithm. (**)

-          Is it APX-complete? (CP ** - AP ***)

-          Can you provide a non-trivial lower bound for the number of colors? (CP ** - AP ***)

-          Can you provide an approximation algorithm for this problem [Some instances of the problem might allow good (low color number) solutions, others not. Find an algorithm that always finds a solution where the maximum number of colors used by the algorithm is at most a factor f worse than the optimal number of colors]. (CP ** - AP ****)

-          Can you come up with a distributed scheduling algorithm where the nodes need to decide themselves without global coordination? (** - ****)

-          Study special cases.

-          Change the problem, and solve that one.

有非平凡的下界？如果这些link离得足够远？

哦，明白了，link的位置是已知的，下界是by n的