圈中t-区间的k-染色问题

On the k-coloring of t-intervals in a cycle

考虑客户请求在圈中实现的问题.每个请求联系着一个t-区间,由圈上至多t(t 1)个区间构成.要实现一个请求,需选择它所对应的t-区间中的一个区间并为其安排k种颜色中的一种.任意两个选定的区间如果在圈上有公共边,则不能得到同一种颜色.对目标寻求实现最大数目的请求问题,给出了一个3.042-近似算法.

The problem satisfying the clients requests in a given cycle is considered. Each request is associated with a t-interval, which consists of up to t（t≥1） intervals on the cycle. To satisfy a request, one of the intervals defining it must be selected and one of k colors must be assigned . No intervals selected for the requests can be assigned with the same color if they shared an edge of the cycle. A 3.042-approximation algorithm is presented for the objective of maximizing the total number of satisfied requests.