报告题目/Title:GeneralLocal Broadcast in Wireless ad hoc Networks via Carrier Sensing
报告人/Speaker：Prof.Yong Zhang 张涌 副研究员 中科院深圳先进技术研究院
时间/Date & Time：Nov.16 (Thursday), 2017, 10:00-10:45
Given a networkwith n nodes. Each node has a message that it wants to deliver to all itsneighbors within the communication range R. The number of distinct messages atnodes in the neighborhood of each node is upper bounded by a parameter k (k canbe a non-constant). The problem is to make each node receive all distinctmessages stored at neighbors, and the objective is minimizing theaccomplishment time. In this paper, we consider theSignal-to-Interference-plus-Noise-Ratio (SINR) model, which is used to depictthe interference in wireless ad hoc networks. With the help of physical carriersensing, we give the optimal protocol with the time complexity $O(k + \log n)$.
报告人简介/About the speaker:
Dr. Yong Zhang iscurrently an Associate Professor in SIAT, CAS. He received his PhD. inDepartment of Computer Science and Engineering at Fudan University in 2007.Before joining SIAT, he worked as Post-Doctoral Fellow and Senior Researcher inTU-Berlin and HKU, respectively. His research interests include design andanalysis of algorithms, combinatorial optimization, wireless networks andalgorithmic game theory. He has published more than 70 papers in refereedjournals and conferences.
报告题目/Title: Minimizing Total WeightedFlow Time with Calibrations
报告人/Speaker：Dr.Vincent Chau 助理研究员 中科院深圳先进技术研究院
时间/Date & Time：Nov.16 (Thursday), 2017, 10:45-11:30
In sensitiveapplications, machines need to be periodically calibrated to ensure that theyrun to high standards. Creating an efficient schedule on these machinesrequires attention to two metrics: ensuring good throughput of the jobs, andensuring that not too much cost is spent on machine calibration. In this paperwe examine flow time as a metric for scheduling with calibrations. Whileprevious papers guaranteed that jobs would meet a certain deadline, we relaxthat constraint to a tradeoff: we want to balance how long the average jobwaits with how many costly calibrations we need to perform.
One advantage ofthis metric is that it allows for online schedules (where an algorithm isunaware of a job until it arrives). We give online algorithms which adapt tojobs as they come. Our online algorithms are constant competitive forunweighted jobs on single or multiple machines, and constant-competitive forweighted jobs on a single machine.
报告人简介/About the speaker:
Vincent Chauobtained his PhD degree at the University of Evry in France in 2014. He wasthen a Postdoctoral Research Fellow at City University of Hong Kong and Hong Kong BaptistUniversity during 2015 and 2016 respectively. He is now Assistant Researcher atShenzhen Institutes of Advanced Technology. His research interest includespower-aware scheduling algorithms, exact and approximation algorithms, onlineand offline algorithms.