Unit:
Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)Library of the School of Science
Author:
Δημητρακόπουλος Θεόδωρος
Supervisors info:
Σταύρος Κολλιόπουλος Αναπλ. Καθηγητής ΕΚΠΑ
Original Title:
Προσεγγιστικοί αλγόριθμοι για το Generalized Min-Sum Set Cover
Translated title:
Approximation algorithms for the Generalized Min-Sum Set Cover
Summary:
In this paper, we study approximation algorithms, based on linear programming,
for the
Generalized Min-Sum Set Cover or Multiple Intents Re-Ranking problem. In this
NP-hard problem, we are given a collection of sets. Each set S has a necessary
cover condition K (S). The goal is to order all the elements of the sets so as
to minimize the total cover time. The cover time of a set S is the least index
i in the ordering such that the first i elements in the ordering contain K(S)
elements in S. Through the study of the premier approximation algorithms for
the problem, we become acquainted with the
evolution and improvement of the techniques that have been developed and the
their impact on the main issue, the performance guarantee.
Keywords:
Linear programming, Generalized min-sum set cover, Performance guarantee, α-points, Matroid
