Entropy Based Framework for Static and Dynamic Coverage and Clustering Problems
Sharma, Puneet
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/87091
Description
Title
Entropy Based Framework for Static and Dynamic Coverage and Clustering Problems
Author(s)
Sharma, Puneet
Issue Date
2008
Doctoral Committee Chair(s)
Beck, Carolyn
Srinivasa Salapaka
Department of Study
Systems and Entrepreneurial Engineering
Discipline
Systems and Entrepreneurial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, System Science
Language
eng
Abstract
In this work, we consider the static and dynamic resource allocation, coverage and clustering problems, and propose a mathematical framework for formulating and solving such problems. The underlying combinatorial optimization problems are solved in a Maximum Entropy Principle (MEP) based framework. The proposed algorithms are computationally efficient and scalable with respect to the size of the underlying data, and are designed to avoid local minima. A characteristic feature of the proposed framework is its ability to detect natural clusters in the underlying data, without the need to initialize it a priori. The notion of coverage is first derived in the static setting and then adapted to the dynamic problem to address the inherent trade-off between the resolution of the clustering solution and the computational complexity. The proposed algorithm for the static problem is successfully implemented to solve the library design problem in combinatorial drug discovery, by addressing the key issues of diversity, representativeness and scalability. In the dynamic problem, the proposed algorithms successfully address the aspects of coverage and tracking. The determination of cluster centers and their associated velocity field is cast as a control design problem to ensure that the algorithm achieves progressively better coverage with time. The proposed algorithm is shown to be five to seven times faster than the frame-by-frame method, with an ability to identify natural clusters in the underlying dataset.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
