Theses and Dissertations

Permanent URI for this collectionhttp://ir.daiict.ac.in/handle/123456789/1

Browse

Filters

2018 - 201912020 - 20231

Settings

Subject: search.filters.subject.Heuristics

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Empirical Study Of Sampling Heuristics For Fairness In Ranking
    (Dhirubhai Ambani Institute of Information and Communication Technology, 2023) Maharaaj, Vinay; Chhaya, Rachit; Rana, Arpit
    Ranking is an important problem for a variety of applications. Classical algorithmsfor ranking may be unfair towards certain group of people or individuals.Fairness may be jeopardized by ranking algorithms that produce discriminatoryresults due to biased data or sampling methods. Hence in the past few years, algorithmsto enforce fairness in ranking have been proposed. However they arecomputationally expensive. Hence it is better to train these on smaller samples ofdata. In this empirical study, multiple sampling strategies for fair ranking algorithmsare compared and evaluated.Uniform sampling, Leverage Score sampling, K -Medoid and Row Norm samplingare the four sampling strategies that are the subject of this study. The thesistests and assesses the effectiveness of various sampling heuristics using a realworlddata set i.e. Yahoo Learning To Rank Challenge Data set.Our work shows that all heuristics perform reasonably well when compared withfull data set, at the same time, giving impressive benefits in terms of computationtime. It is an open question to obtain some theoretical guarantees for these samplingstrategies for fair ranking algorithms.
  • Thumbnail Image
    ItemOpen Access
    The Study of Cycles in 2-connected Graphs Specifically Odd Graphs
    (Dhirubhai Ambani Institute of Information and Communication Technology, 2018) Thakker, Avani; Muthu, Rahul
    Counting the number of cycles in an undirected graph is a classical problemwhich is known to be intractable and so research on this problem typically focuses on approximation algorithms, special cases, heuristics and some variants of the problem. This problem has been extensively studied for its applications in areas of communication systems, artificial intelligence and signal processing. In Complexity theory, this problem lies in the class of #P-complete problem. There may be exponentially many simple cycles in a graph. We observed growth in the number of cycles by adding ears to a 2-connected graph. As analyzed, the growth was exponential. Counting or finding cycles and paths of graphs like complete graphs, presents no interest, in particular since everything is already known analytically. Hence, we studied the cycle structure in Odd Graphs. We analytically obtained cycle lengths that are certainly present in an odd graph without traversing the graph structure. Further, we added minimal number of edges to an odd graph to make the graph pancyclic.