2026-09-19T18:59:52Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/26347 2023-07-10 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

Kiyavash, Negar Kumar, P.R. Truong, Anh 2011-08-26T15:24:21Z 2013-08-27T10:00:24Z 2011-08-26T15:24:21Z 2011-08 In the first part of this thesis, we consider a proposed Quality of Service (QoS) model in which a set of clients require their own timely-throughput from an access point, with packet deadlines restricted to be in one period. It is known that two debt-based policies, including time-based debt and weighted delivery-based debt, are feasibility optimal in the sense that they can fulfill the requirements of all sets of feasible clients. We analyze why these poli- cies are optimal by considering a class of periodwise static priority policies. We prove that this latter class of policies can achieve whatever a history- dependent policy can, i.e., it suffices to consider only this class of policies for such a scheduling problem. Our approach proceeds by investigating the submodularity of the complement of the idle time function. We thereby show that the set defined by the timely-throughput constraints is a polymatroid, from which the optimality within the class of periodwise static priority poli- cies follows. The second part of the thesis analyzes the convergence of an algorithm for the problem of learning with expert advice. At the present time, several web-based recommendation systems use votes from experts or other users to recommend objects to other customers. We apply the `learning from expert advice' framework for this system, and propose a recommendation algorithm that uses a weighted update rule. Often, recommendation algorithms make assumptions that do not hold in practice, such as requiring a large number of good objects, presence of experts with the identical taste as the user receiving the recommendation, or experts who vote on all or a majority of objects. Our algorithm relaxes these assumptions by allowing an arbitrary proportion of bad objects as well as arbitrary tastes of experts. Moreover, it can deal with the issues that arise because of the existence of sleeping-experts, i.e., experts who are not available for voting at all rounds. A key attribute of our approach is to define the concept of the best expert on the basis of both availability and accuracy of experts. We then prove that the algorithm converges almost surely to the best expert(s) regardless of whether the predictions of experts are binary or continuous valued. Moreover, we derive an upper bound on loss of the proposed algorithm by comparing it to the loss of an appropriately defined `current best' and show that the regret of our algorithm is logarithmic in the number of experts. Besides theoretical performance guarantees, we present simulation results that show the proposed algorithm outperforms Dsybil, the current state-of-the-art recommendation algorithm. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-07-19T17:03:42Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Truong_Anh.pdf: 379795 bytes, checksum: 92f07d4bbfa6903f4fc7a96c5b90e7ea (MD5) Made available in DSpace on 2011-08-26T15:24:21Z (GMT). No. of bitstreams: 2 Truong_Anh.pdf: 379795 bytes, checksum: 92f07d4bbfa6903f4fc7a96c5b90e7ea (MD5) license.txt: 4059 bytes, checksum: 98a39a915f69f713a82b15258837ca40 (MD5) Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by William Ingram (wingram2@illinois.edu) on 2011-08-26T15:26:18Z Item is restricted until 2013-08-26T15:25:28Z Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2013-08-27T10:00:24Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Electrical and Computer Engineering (ID: 446) No. of bitstreams: 3 Truong_Anh.pdf.txt: 56514 bytes, checksum: ea59cc16b952735156b011d642d9798e (MD5) Truong_Anh.pdf: 379795 bytes, checksum: 92f07d4bbfa6903f4fc7a96c5b90e7ea (MD5) license.txt: 4059 bytes, checksum: 98a39a915f69f713a82b15258837ca40 (MD5) Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2013-08-27T10:00:24Z http://hdl.handle.net/2142/26347 en Copyright 2011 Anh Truong QoS scheduling randomized policies feasibility optimal priority policies submodularity polymatroid learning with experts weighted average prediction availability accuracy convergence sleeping experts recommendation system. Quality of Service (QoS) Feasibility optimality of periodwise static priority policies for a quality of service model in wireless networks and convergence analysis for an online recommendation system Electrical & Computer Eng 1933 Electrical & Computer Engr 1200 University of Illinois at Urbana-Champaign Thesis M.S. PHD:Electr & Computer Eng-UIUC 10KS1200PHD