Perfect Circular Arc Coloring

The circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n² m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem.Partially supported by Project 02139 of Education Ministry of China.Supported in part by the Research Grants Council of Hong Kong (Project No. HKU7054/03P) and a seed funding for basic research of HKU.     

Finding nucleolus of flow game

We study the algorithmic issues of finding the nucleolus of a flow game. The flow game is a cooperative game defined on a network D=(V,E;ω). The player set is E and the value of a coalition S⊆E is defined as the value of a maximum flow from source to sink in the subnetwork induced by S. We show that the nucleolus of the flow game defined on a simple network (ω(e)=1 for each e∈E) can be computed in polynomial time by a linear program duality approach, settling a twenty-three years old conjecture by Kalai and Zemel. In contrast, we prove that both the computation and the recognition of the nucleolus are -hard for flow games with general capacity. Supported by NCET, NSFC (10771200), a CERG grant (CityU 1136/04E) of Hong Kong RGC, an SRG grant (7001838) of City University of Hong Kong.     

Bin packing under linear constraints

In this paper, we study a bin packing problem in which the sizes of items are determined by k linear constraints, and the goal is to decide the sizes of items and pack them into a minimal number of unit sized bins. We first provide two scenarios that motivate this research. We show that this problem is NP-hard in general, and propose several algorithms in terms of the number of constraints. If the number of constraints is arbitrary, we propose a 2-approximation algorithm, which is based on the analysis of the Next Fit algorithm for the bin packing problem. If the number of linear constraints is a fixed constant, then we obtain a PTAS by combining linear programming and enumeration techniques, and show that it is an optimal algorithm in polynomial time when the number of constraints is one or two. It is well known that the bin packing problem is strongly NP-hard and cannot be approximated within a factor 3 / 2 unless P = NP. This result implies that the bin packing problem with a fixed number of constraints may be simper than the original bin packing problem. Finally, we discuss the case when the sizes of items are bounded.     

An Approximation Scheme for Bin Packing with Conflicts

In this paper we consider the following bin packing problem with conflicts. Given a set of items V = {1,..., n} with sizes s₁,..., s (0,1) and a conflict graph G = (V, E), we consider the problem to find a packing for the items into bins of size one such that adjacent items (j, j) E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem.We propose an asymptotic approximation scheme for the bin packing problem with conflicts restricted to d-inductive graphs with constant d. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm finds an assignment for the items such that the generated number of bins is within a factor of (1 + ) of optimal provided that the optimum number is sufficiently large. The running time of the algorithm is polynomial both in n and in .     

Online interval scheduling: randomized and multiprocessor cases

We consider the problem of scheduling a set of equal-length intervals arriving online, where each interval is associated with a weight and the objective is to maximize the total weight of completed intervals. An optimal 4-competitive algorithm has long been known in the deterministic case, but the randomized case remains open. We give the first randomized algorithm for this problem, achieving a competitive ratio of 3.5822. We also prove a randomized lower bound of 4/3, which is an improvement over the previous 5/4 result. Then we show that the techniques can be carried to the deterministic multiprocessor case, giving a 3.5822-competitive 2-processor algorithm, and a 4/3 lower bound for any number of processors. We also give a lower bound of 2 for the case of two processors. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 176–186. The work described in this paper was fully supported by a grant from City University of Hong Kong (SRG 7001969), and NSFC Grant No. 70525004 and 70702030.     

Bin packing with “Largest In Bottom” constraint: tighter bounds and generalizations

The (online) bin packing problem with LIB constraint is stated as follows: The items arrive one by one, and must be packed into unit capacity bins, but a bigger item cannot be packed into a bin which already contains a smaller item. The number of used bins has to be minimized as usually. We show that the absolute performance bound of algorithm First Fit is not worse than 2+1/6≈2.1666 for the problem, improving the previous best upper bound 2.5. Moreover, if the item sizes do not exceed 1/d, then we improve the previous best result 2+1/d to 2+1/d(d+2), for any d≥2. (Both previously best results are due to Epstein, Nav. Res. Logist. 56(8):780–786, 2009.) Furthermore, we define a problem with the generalized LIB constraint, where some incoming items cannot be packed into the bins of some already packed items. The (in)compatibility of the incoming item with the items already packed becomes known only at the arrival of the actual item, and is given by an undirected graph (and, as usual in case of online graph problems, we can see only that part of the graph what already arrived). We show that 3 is an upper bound for this general problem if some natural transitivity constraint is satisfied.     

Online bin packing problem with buffer and bounded size revisited

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within \((\alpha ,1/2]\) where \(0 \le \alpha < 1/2 \), and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360–369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.     

A PTAS for Semiconductor Burn-in Scheduling

In this paper a polynomial time approximation scheme, PTAS for short, is presented for the problem of scheduling jobs in a batch processing system. Each job has a pre-defined release date, which indicates when the job is available, and a pre-defined burn-in time, which is the least time needed for processing the job. At one time, at most B jobs can be processed together, where B is a pre-given number. No preemption is permitted.Research supported in part by an RGC CERG grant [CityU 1081/02E] and a grant from CityU [7001347].Supported by the fund from NSFC under grant numbers 10271065 and 60373025.     

A note on online strip packing

In online strip packing we are asked to pack a list of rectangles one by one into a vertical strip of unit width, without any information about future rectangles. The goal is to minimize the total height of strip used. The best known algorithm is First Fit Shelf algorithm (Baker and Schwarz in SIAM J. Comput. 12(3):508–525, 1983), which has an absolute competitive ratio of 6.99 under the assumption that the height of each rectangle is bounded from above by one. We improve the shelf algorithm and show an absolute competitive ratio of without the restriction on rectangle heights. Our algorithm also beats the best known online algorithm for parallel job scheduling. Ye’s research supported by NSFC(10601048). Zhang’s research supported by NSFC(60573020).     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity

We study the problem of on-line scheduling jobs with release dates on a batch machine of finite capacity with the objective of minimizing the makespan. We generalize several existing algorithms for the problem to a class of on-line algorithms that are 2-competitive for any arbitrary finite machine capacity. Then, we show that one of these generalized algorithms is in fact 7/4-competitive for machine capacity 2. This is the first on-line algorithm for a finite machine capacity with competitive ratio less than 2.This research is substantially supported by a grant from City Univ. of Hong Kong (Grant No. 7001119). The second author is supported by this grant and by the Natural Science Foundation of China.     

Inverse maximum flow problems under the weighted Hamming distance

In this paper, we consider inverse maximum flow problem under the weighted Hamming distance. Four models are studied: the problem under sum-type weighted Hamming distance; the problem under bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times.Research supported by the National Natural Science Foundation of China (60021201), and the Hong Kong Research Grant Council under CERG CityU 9041091 and CUHK 103105.     

A two-phase algorithm for bin stretching with stretching factor 1.5

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin.We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We build on previous algorithms and use a two-phase approach. However, our analysis is technically more complicated and uses amortization over the bins with the help of two weight functions.     

Min-energy voltage allocation for tree-structured tasks

We study job scheduling on processors capable of running at variable voltage/speed to minimize energy consumption. Each job in a problem instance is specified by its arrival time and deadline, together with required number of CPU cycles. It is known that the minimum energy schedule for n jobs can be computed in O(n³) time, assuming a convex energy function. We investigate more efficient algorithms for computing the optimal schedule when the job sets have certain special structures. When the time intervals are structured as trees, the minimum energy schedule is shown to have a succinct characterization and is computable in time O(P) where P is the tree’s total path length. We also study an on-line average-rate heuristics AVR and prove that its energy consumption achieves a small constant competitive ratio for nested job sets and for job sets with limited overlap. Some simulation results are also given. This work is supported in part by Research Grants Council of Hong Kong under grant No. CityU 1165/04E, National Natural Science Foundation of China under Grant No. 60135010, 60321002 and the Chinese National Key Foundation Research & Development Plan (2004CB318108).     

A Tighter Extra-Resource Analysis of Online Deadline Scheduling

This paper is concerned with online algorithms for scheduling jobs with deadlines on a single processor. It has been known for long that unless the system is underloaded, no online scheduling algorithm can be 1-competitive, i.e., matching the performance of the optimal offline algorithm. Nevertheless, recent work has revealed that some online algorithms using a moderately faster processor (or extra processors) can guarantee very competitive performance Kalyanasundaram and Pruhs, 2000 or even be 1-competitive Koo et al., 2002; Lam and To, 2001. This paper takes a further step to investigate online scheduling algorithms with an even higher performance guarantee (i.e., better than 1-competitive algorithms) and in particular, presents an extra-resource analysis of the earliest-deadline-first strategy (EDF) with respect to such a higher performance guarantee.A preliminary version of this paper has been accepted by The Australian Theory Symposium on Computing, 2004.This research was supported in part by Hong Kong RGC Grant HKU-7024/01E.     

Opportunistic data structures for range queries

In this paper, we study the problem of supporting range sum queries on a compressed sequence of values. For a sequence of n k-bit integers, k ≤ O(log n), our data structures require asymptotically the same amount of storage as the compressed sequence if compressed using the Lempel-Ziv algorithm. The basic structure supports range sum queries in O(log n) time. With an increase by a constant factor in the storage complexity, the query time can be improved to O(log log n + k). The work described in this paper is fully supported by a grant from the Research Grant Council of the Hong Kong Special Administrative Region, China (CityU 1071/02E). A preliminary version has appeared in 11th International Conference in Computing and Combinatorics (COCOON'05).     

Semi-online scheduling with “end of sequence” information

We study a variant of classical scheduling, which is called scheduling with “end of sequence” information. It is known in advance that the last job has the longest processing time. Moreover, the last job is marked, and thus it is known for every new job whether it is the final job of the sequence. We explore this model on two uniformly related machines, that is, two machines with possibly different speeds. Two objectives are considered, maximizing the minimum completion time and minimizing the maximum completion time (makespan). Let s be the speed ratio between the two machines, we consider the competitive ratios which are possible to achieve for the two problems as functions of s. We present algorithms for different values of s and lower bounds on the competitive ratio. The proposed algorithms are best possible for a wide range of values of s. For the overall competitive ratio, we show tight bounds of ϕ + 1 ≈ 2.618 for the first problem, and upper and lower bounds of 1.5 and 1.46557 for the second problem. The authors would like to dedicate this paper to the memory of our colleague and friend Yong He who passed away in August 2005 after struggling with illness. D. Ye: Research was supported in part by NSFC (10601048).     

A New delay control method for real-time flows

This paper presents a novel control algorithm to decrease the worst-case delay bound for high rate homogeneous and heterogeneous real-time flows when the network traffic load becomes heavy. The algorithm is adaptive based on the instantaneous network situations. It employs a generalized form of traditional (σ,ρ) regulator called the generalized (σ,ρ,λ) regulator that operates like the (σ,ρ) regulator under the normal network traffic load situation, but provides more regulations for the heavy network traffic load situation. For a set of real-time flows, we can show that D _rg ≤D _g where D _rg and D _g are the worst-case delay bounds with the (σ,ρ,λ) regulator and the (σ,ρ) regulator respectively. More specifically, we have developed a set of formulas to set the parameters for the new regulator so as to reduce the worst-case delay bounds for the real-time flows. We can prove that there exists a threshold input rate ρ^* such that D _rg = D _g for ρ≤ρ^* and D _rg < D _g for ρ > ρ^*. When the average input rate of real-time flows is very high, the generalized regulator can effectively control the delay. The extensive experiment data match our theoretical results. The part of this paper has been appeared in The 23 ^rd IEEE International Conference on Distributed Computing Systems, 2003. The work is supported by CityU strategic grant Nos: 7001777 and 7001709 and CityU ARP Project No. 9610027. H. Wang was partially supported by National Natural Science Foundation of China (10471088, 60572126) and CityU strategic grant no. 7001709. Wanqing Tu is now with Department of Computer Science, The Hong Kong University of Science and Technology. Clear Water Bay, New Territories, Kowloon, Hong Kong.     

Min-Sum Bin Packing

We study min-sum bin packing (MSBP). This is a bin packing problem, where the cost of an item is the index of the bin into which it is packed. The problem is equivalent to a batch scheduling problem we define, where the total completion time is to be minimized. The problem is NP-hard in the strong sense. We show that it is not harder than this by designing a polynomial time approximation scheme for it. We also show that several natural algorithms which are based on well-known bin packing heuristics (such as First Fit Decreasing) fail to achieve an asymptotic finite approximation ratio, whereas Next Fit Increasing has an absolute approximation ratio of at most 2, and an asymptotic approximation ratio of at most 1.6188. We design a new heuristic that applies Next Fit Increasing on the relatively small items and adds the larger items using First Fit Decreasing, and show that its asymptotic approximation ratio is at most 1.5604.