19 citations · 34 across the 15 of their papers we have counts for
23 papers
Matchings under One-Sided Preferences with Soft Quotas
Santhini K A, Raghu Raman Ravi, Meghana Nasre
Assigning applicants to posts in the presence of applicant preferences and quotas associated with posts is extensively investigated. For a post, a lower quota guarantees, and an up…
Stability Notions for Hospital Residents with Sizes
Haricharan Balasundaram, J B Krishnashree, Girija Limaye +1
The Hospital Residents problem with sizes (HRS) is a generalisation of the well-studied hospital residents (HR) problem. In the HRS problem, an agent a has a size s(a) and the agen…
Generalized Capacity Planning for the Hospital-Residents Problem
Haricharan Balasundaram, Girija Limaye, Meghana Nasre +1
The Hospital Residents setting models important problems like school choice, assignment of undergraduate students to degree programs, among many others. In this setting, fixed quot…
Optimal Capacity Modification for Stable Matchings with Ties
Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar
We consider the Hospitals/Residents (HR) problem in the presence of ties in hospital preferences. Among the three notions of stability, namely weak stability, strong stability, and…
Group Fairness and Multi-criteria Optimization in School Assignment
Santhini K. A., Kamesh Munagala, Meghana Nasre +1
We consider the problem of assigning students to schools, when students have different utilities for schools and schools have capacity. There are additional group fairness consider…
Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan
We study the many-to-many bipartite matching problem in the presence of preferences where ties, as well as lower quotas, may appear on both sides of the bipartition. The input is a…
Online Algorithms for Matchings with Proportional Fairness Constraints and Diversity Constraints
Anand Louis, Meghana Nasre, Prajakta Nimbhorkar +1
Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. More…
Popular Critical Matchings in the Many-to-Many Setting
Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan +1
We consider the many-to-many bipartite matching problem in the presence of two-sided preferences and two-sided lower quotas. The input to our problem is a bipartite graph G=(A U B,…
Matchings with Group Fairness Constraints: Online and Offline Algorithms
Govind S. Sankar, Anand Louis, Meghana Nasre +1
We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this…
Envy-free matchings with cost-controlled quotas
Girija Limaye, Meghana Nasre
We consider the problem of assigning agents to programs in the presence of two-sided preferences, commonly known as the Hospital Residents problem. In the standard setting each pro…
Envy-freeness and Relaxed Stability under lower quotas
Prem Krishnaa, Girija Limaye, Meghana Nasre +1
We consider the problem of matchings under two-sided preferences in the presence of maximum as well as minimum quota requirements for the agents. This setting, studied as the Hospi…
Trade-offs in dynamic coloring for bipartite and general graphs
Manas Jyoti Kashyop, N. S. Narayanaswamy, Meghana Nasre +1
We present trade-offs in the incremental and fully dynamic settings to maintian a proper coloring. For any fully dynamic -coloring algorithm, the maximum of the update time, num…
Dichotomy Results for Classified Rank-Maximal Matchings and Popular Matchings
Meghana Nasre, Prajakta Nimbhorkar, Nada Pulath
In this paper, we consider the problem of computing an optimal matching in a bipartite graph where elements of one side of the bipartition specify preferences over the other side,…
How good are Popular Matchings?
Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar +1
In this paper, we consider the Hospital Residents problem (HR) and the Hospital Residents problem with Lower Quotas (HRLQ). In this model with two sided preferences, stability is a…
Popular Matching with Lower Quotas
Meghana Nasre, Prajakta Nimbhorkar
We consider the well-studied Hospital Residents (HR) problem in the presence of lower quotas (LQ). The input instance consists of a bipartite graph $G = (\mathcal{R} \cup \mathcal{…
Popularity in the generalized Hospital Residents Setting
Meghana Nasre, Amit Rawat
We consider the problem of computing popular matchings in a bipartite graph G = (R U H, E) where R and H denote a set of residents and a set of hospitals respectively. Each hospita…
Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran
We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph G=(V,E) with positive edge weights. F…
Rank Maximal Matchings -- Structure and Algorithms
Pratik Ghoshal, Meghana Nasre, Prajakta Nimbhorkar
Let G = (A U P, E) be a bipartite graph where A denotes a set of agents, P denotes a set of posts and ranks on the edges denote preferences of the agents over posts. A matching M i…
Betweenness Centrality -- Incremental and Faster
Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran
We consider the incremental computation of the betweenness centrality of all vertices in a large complex network modeled as a graph G = (V, E), directed or undirected, with positiv…
Popular Matchings -- structure and cheating strategies
Meghana Nasre
We consider the cheating strategies for the popular matchings problem. The popular matchings problem can be defined as follows: Let G = (A U P, E) be a bipartite graph where A deno…
Hardness and Parameterized Algorithms on Rainbow Connectivity problem
Prabhanjan Ananth, Meghana Nasre, Kanthi K Sarpatwar
A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists…
New Hardness Results in Rainbow Connectivity
Prabhanjan Ananth, Meghana Nasre
A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists…
Popularity at Minimum Cost
Telikepalli Kavitha, Meghana Nasre, Prajakta Nimbhorkar
We consider an extension of the {\em popular matching} problem in this paper. The input to the popular matching problem is a bipartite graph G = (A U B,E), where A is a set of peop…