Finding Maximum Regret Ratio Minimizing Sets of Minimized Size

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Finding Maximum Regret Ratio Minimizing Sets of Minimized Size"

by

Sepanta ZEIGHAMI

Abstract:

From providing suggestions to users to summarizing the information in the 
database, selecting a subset of points from a database that are 
representative of the information in the database is a problem with many 
applications. Looking at the problem of selecting such a representative 
set from the perspective of the users, it is important to include the 
datapoints in the set that ensure that all the users are satisfied with 
the set, at least to a certain extent. In this project, we discuss how the 
satisfaction of the users can be quantified and we propose an algorithm by 
which a subset of the database can be selected that guarantees that all 
the users are satisfied with the selected points to a desired extent. We 
prove that our algorithm is an O(dlogn)-approximation algorithm, where d 
and n are the dimensionality and size of the database respectively. We, 
furthermore, prove that the problem we address is NP-Hard and we 
complement our theoretical results with empirical studies that show the 
effectiveness of our algorithm in practice.

Date                 : 24 April 2017 (Mon)

Time                 : 17:00 - 18:00

Venue                : 2128C (via lift 19)

Advisor              : Dr. Raymond WONG

2nd Reader           : Dr. Wilfred NG