W3CHINA.ORG讨论区--[讨论]给大家出一个博士生面试题，希望可以充实大家的生活

贴子主题： [讨论]给大家出一个博士生面试题，希望可以充实大家的生活

本主题类别:

Interview Problem 103: SINR Scheduling

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.


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	140.625ms