Entropy Based Framework for Static and Dynamic Coverage and Clustering Problems

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Systems and Entrepreneurial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Sharma, Puneet

Contributors dc:contributor

• Beck, Carolyn
• Srinivasa Salapaka

• Engineering, System Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI3337919

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/87091