Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
For a set S of intervals, the clique-interval IS is defined as the interval obtained from the intersection of all the intervals in S, and the clique-width quantity wS is defined as the length of IS. Given a set S of intervals, it is straightforward to compute its clique-interval and clique-width. In this paper we study the problem of partitioning a set of intervals in order to maximize the sum of the clique-widths of the partitions. We present an O(n log n) time algorithm for the balanced bipartitioning problem, and an O(kn2) time algorithm for the k-way unbalanced partitioning problem.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
Charles Micchelli
Journal of Approximation Theory