Online bin packing of fragile objects with application in cellular networks

We study a specific bin packing problem which arises from the channel assignment problems in cellular networks. In cellular communications, frequency channels are some limited resource which may need to share by various users. However, in order to avoid signal interference among users, a user needs to specify to share the channel with at most how many other users, depending on the user’s application. Under this setting, the problem of minimizing the total channels used to support all users can be modeled as a specific bin packing problem as follows: Given a set of items, each with two attributes, weight and fragility. We need to pack the items into bins such that, for each bin, the sum of weight in the bin must be at most the smallest fragility of all the items packed into the bin. The goal is to minimize the total number of bins (i.e., the channels in the cellular network) used. We consider the on-line version of this problem, where items arrive one by one. The next item arrives only after the current item has been packed, and the decision cannot be changed. We show that the asymptotic competitive ratio is at least 2. We also consider the case where the ratio of maximum fragility and minimum fragility is bounded by a constant. In this case, we present a class of online algorithms with asymptotic competitive ratio at most of 1/4+3r/2, for any r>1. A preliminary version of this paper appeared in Proc. of Workshop on Internet and Network Economics (WINE’05, pp. 564–573). The research of W.-T.C. was supported in part by Hong Kong RGC grant HKU5172/03E. The research of F.Y.-L.C. was supported in part by Hong Kong RGC Grant HKU7142/03E. The research of D.Y. was supported by NSFC (10601048). The research of G.Z. was supported in part by NSFC (60573020).     

Approximation schemes for two-machine flow shop scheduling with two agents

In this paper we consider two-machine flow shop scheduling with two agents. Two models are investigated. One is the weighted-sum optimization model and the other is the constrained optimization model. For the former, we show that it is weakly NP-hard and propose a fully polynomial time approximation scheme. For the latter, we also show the problem is weakly NP-hard. With violating the constraint a factor of ?? a fully polynomial time approximation scheme is provided.     

期望理论述评

期望理论是激励理论中十分重要的内容。期望理论对员工工作动机的主要方面进行了深刻分析 ,揭示了其内在必然性。期望理论的研究过程和研究结论对企业员工激励机制的建立、发展目标的确定、员工培训及企业决策过程有着非常重要的意义     

Online lazy bureaucrat scheduling with a machine deadline

The lazy bureaucrat scheduling problem was first introduced by Arkin et al. (Inf Comput 184:129–146, 2003). Since then, a number of variants have been addressed. However, very little is known on the online version. In this note we focus on the scenario of online scheduling, in which the jobs arrive over time. The bureaucrat (machine) has a working time interval. Namely, he has a deadline by which all scheduled jobs must be completed. A decision is only based on released jobs without any information on the future. We consider two objective functions of [min-makespan] and [min-time-spent]. Both admit best possible online algorithms with competitive ratio of \(\frac{\sqrt{5}+1}{2}\approx 1.618\).     

建立我国水资源保护税制之构想

水资源保护税是对水资源的使用及水资源污染进行的征税,它通过价值机制促使水资源实现价值最大化从而实现水资源的有效配置。水资源保护税的设计取决于它所要达到的目标,即一定能使水资源保护税对企业和消费者的水资源消费行为和污染行为产生影响,从而实现其预定的目标。水资源保护税的设计主要从税基、税收主体、征税对象、征税环节、税率、征税手段、纳税期限等方面来实现其目的。     

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).     

神经功能保护治疗仪的压控恒流源电路的研制

本文设计的单极性输入双极性输出压控恒流源电路是神经保护治疗仪的重要组成部分,它由CPLD电路产生极性相反的脉冲控制三极管组成的电流换向开关来选择输出极性。其V/I转换系数、带负载能力(包括输出电流的大小及负载电阻的大小范围)可以通过合理设计电路参数来实现,实验证明,该恒流源电路具有良好的线性和电气安全性,能很好的满足神经功能保护治疗仪的要求。     

On lazy bureaucrat scheduling with common deadlines

Lazy bureaucrat scheduling is a new class of scheduling problems introduced by Arkin et al. (Inf. Comput. 184:129–146, 2003). In this paper we focus on the case where all the jobs share a common deadline. Such a problem is denoted as CD-LBSP, which has been considered by Esfahbod et al. (Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66, 2003). We first show that the worst-case ratio of the algorithm SJF (Shortest Job First) is two under the objective function [min-time-spent], and thus answer an open question posed in (Esfahbod, et al. in Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66, 2003). We further present two approximation schemes A _k and B _k both having worst-case ratio of , for any given integer k>0, under the objective functions [min-makespan] and [min-time-spent], respectively. Finally, we prove that the problem CD-LBSP remains NP-hard under several objective functions, even if all jobs share the same release time. A preliminary version of the paper appeared in Proceedings of the 7th Latin American Symposium on Theoretical Informatics, pp 515–523, 2006. Research of G. Zhang supported in part by NSFC (60573020).     

Preface

Journal of Combinatorial Optimization -     

From packing rules to cost-sharing mechanisms

Journal of Combinatorial Optimization - Bin packing is one of the most fundamental problems in resource allocation. Most research on the classical bin packing problem has focused on the design and...