By Allan Borodin (auth.), Siu-Wing Cheng, Chung Keung Poon (eds.)
This booklet constitutes the refereed lawsuits of the second one foreign convention on Algorithmic points in details and administration, AAIM 2006, held in Hong Kong, China in June 2006.
The 34 revised complete papers provided including abstracts of two invited talks have been rigorously reviewed and chosen from 263 submissions. The papers conceal themes from parts equivalent to on-line scheduling, video game and finance, information constructions and algorithms, computational geometry, optimization, graph, and string.
Read or Download Algorithmic Aspects in Information and Management: Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings PDF
Similar international conferences and symposiums books
This booklet comprises the papers provided on the ninth overseas Workshop on box ProgrammableLogic and purposes (FPL’99), hosted via the college of Strathclyde in Glasgow, Scotland, August 30 – September 1, 1999. FPL’99 is the 9th within the sequence of annual FPL workshops. The FPL’99 programme committee has been lucky to have got a good number of high quality papers addressing quite a lot of themes.
This booklet constitutes the refereed lawsuits of the seventh foreign convention on common sense Programming and Nonmonotonic Reasoning, LPNMR 2004, held in castle Lauderdale, Florida, united states in January 2004. The 24 revised complete papers offered including eight procedure descriptions have been rigorously reviewed and chosen for presentation.
- Progress in Galois Theory: Proceedings of John Thompson's 70th Birthday Conference (Developments in Mathematics)
- Digital Mammography: 9th International Workshop, IWDM 2008 Tucson, AZ, USA, July 20-23, 2008 Proceedings
- Proceedings Of The Sixth International Workshop: Proceedings Of The Sixth International Workshop
- Trust Management: Third International Conference, iTrust 2005, Paris, France, May 23-26, 2005. Proceedings
- Database: Enterprise, Skills and Innovation: 22nd British National Conference on Databases, BNCOD 22, Sunderland, UK, July 5-7, 2005. Proceedings
- Quanta and Reality: a Symposium for the Non Scientist on the Physical and Philosophical Implications of Quantum Mechanics
Extra resources for Algorithmic Aspects in Information and Management: Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006. Proceedings
The omitted proofs will be included in the full paper. Lemma 6. L1 ≤ l1 . Furthermore, if L1 = l1 , then C1,min > C1,max ; if L1 = l1 − 12 , then C1,max ≥ C1,max . Lemma 7. Li ≤ li for i = 1, . . , k. Furthermore, if Li = li , then Ci,min > Ci,max ; if Li = li − 12 , then Ci,max ≥ Ci,max . Theorem 3. The competitive ratio of algorithm M EDF is 32 . Proof. Now we consider the last period. By Lemma 7, we have Lk ≤ lk . It is easy to verify ak ≤ 3. Otherwise if we schedule the last ak jobs at Ck,min using EDF , then the last job is not a critical job.
An interesting extension of the problem considered in this paper may take into account the non-uniform time windows. That is, each of the requests has a diﬀerent size of time window. ) to see if better bounds can be obtained. Other possible extension of the problem is to crew scheduling in which more than one server is used to serve the requests. All of these can be further investigated. 70525004). References 1. , and Marchetti-Spaccamela et al. Non-abusiveness helps: An o(1)-competitive algorithm for minimizing the maximum ﬂow time in the online traveling salesman problem.
So we have d2 < Ck,min + 1. By the algorithm after the deletion of job j1 , it is still a counterexample. It is a contradiction. Thus d1 = Ck,max + 1. If Lk = lk , then Ck,min > Ck,max . We get bk ≤ 2 and Lk ≤ 12 (fk + 1); If Lk ≤ lk − 12 , then bk ≤ 3. Hence Lk ≤ 12 (fk + 1). Case 3. If ak = 2, then the last job must have deadline Ck,max + 2. Otherwise if we schedule the last two jobs at Ck,min using EDF , then the last job is not a critical job. After the deletion of the last job, it is still a counterexample.