BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Prajakta Nimbhorkar

Prajakta Nimbhorkar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityComputer Science and Game TheoryDiscrete Mathematics

Catalog footprint

What is connected

6works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2023arXiv

Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings

We study the fair allocation of indivisible goods and chores under ordinal valuations for agents with unequal entitlements. We show the existence and polynomial time computation of weighted necessarily proportional up to one item (WSD-PROP1) allocations for both goods and chores, by reducing it to a problem of finding perfect matchings in a bipartite graph. We give a complete characterization of these allocations as corner points of a perfect matching polytope. Using this polytope, we can optimize over all allocations to find a min-cost WSD-PROP1 allocation of goods or most efficient WSD-PROP1 allocation of chores. Additionally, we show the existence and computation of sequencible (SEQ) WSD-PROP1 allocations by using rank-maximal perfect matching algorithms and show incompatibility of Pareto optimality under all valuations and WSD-PROP1. We also consider the Best-of-Both-Worlds (BoBW) fairness notion. By using our characterization, we show the existence and polynomial time computation of Ex-ante envy free (WSD-EF) and Ex-post WSD-PROP1 allocations under ordinal valuations for both chores and goods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Envy-freeness and Relaxed Stability under lower quotas

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 Hospital Residents with Lower Quotas (HRLQ) in literature, models important real world problems like assigning medical interns (residents) to hospitals, and teaching assistants to instructors where a minimum guarantee is essential. When there are no minimum quotas, stability is the de-facto notion of optimality. However, in the presence of minimum quotas, ensuring stability and simultaneously satisfying lower quotas is not an attainable goal in many instances. To address this, a relaxation of stability known as envy-freeness, is proposed in literature. In our work, we thoroughly investigate envy-freeness from a computational view point. Our results show that computing envy-free matchings that match maximum number of agents is computationally hard and also hard to approximate up to a constant factor. Additionally, it is known that envy-free matchings satisfying lower-quotas may not exist. To circumvent these drawbacks, we propose a new notion called relaxed stability. We show that relaxed stable matchings are guaranteed to exist even in the presence of lower-quotas. Despite the computational intractability of finding a largest matching that is feasible and relaxed stable, we give efficient algorithms that compute a constant factor approximation to this matching in terms of size.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Rank Maximal Matchings -- Structure and Algorithms

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 in G is rank-maximal if it matches the maximum number of applicants to their top-rank post, subject to this, the maximum number of applicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximal matchings, which is a useful tool that encodes all rank-maximal matchings in an instance. The characterization leads to simple and efficient algorithms for several interesting problems. In particular, we give an efficient algorithm to compute the set of rank-maximal pairs in an instance. We show that the problem of counting the number of rank-maximal matchings is #P-Complete and also give an FPRAS for the problem. Finally, we consider the problem of deciding whether a rank-maximal matching is popular among all the rank-maximal matchings in a given instance, and give an efficient algorithm for the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

Let $G =<S>$ be a solvable permutation group of the symmetric group $S_n$ given as input by the generating set $S$. We give a deterministic polynomial-time algorithm that computes an \emph{expanding generating set} of size $\tilde{O}(n^2)$ for $G$. More precisely, the algorithm computes a subset $T\subset G$ of size $\tilde{O}(n^2)(1/λ)^{O(1)}$ such that the undirected Cayley graph $Cay(G,T)$ is a $λ$-spectral expander (the $\tilde{O}$ notation suppresses $\log ^{O(1)}n$ factors). As a byproduct of our proof, we get a new explicit construction of $\varepsilon$-bias spaces of size $\tilde{O}(n\poly(\log d))(\frac{1}{\varepsilon})^{O(1)}$ for the groups $\Z_d^n$. The earlier known size bound was $O((d+n/\varepsilon^2))^{11/2}$ given by \cite{AMN98}.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Log-space Algorithms for Paths and Matchings in k-trees

Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 [JT07]. However, for graphs of tree-width larger than 2, no bound better than NL is known. In this paper, we improve these bounds for k-trees, where k is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed k-trees, and for computation of shortest and longest paths in directed acyclic k-trees. Besides the path problems mentioned above, we also consider the problem of deciding whether a k-tree has a perfect macthing (decision version), and if so, finding a perfect match- ing (search version), and prove that these two problems are L-complete. These problems are known to be in P and in RNC for general graphs, and in SPL for planar bipartite graphs [DKR08]. Our results settle the complexity of these problems for the class of k-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of divide-and-conquer approach in log-space, along with some ideas from [JT07] and [LMR07].

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Popularity at Minimum Cost

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 people, B is a set of items, and each person a belonging to A ranks a subset of items in an order of preference, with ties allowed. The popular matching problem seeks to compute a matching M* between people and items such that there is no matching M where more people are happier with M than with M*. Such a matching M* is called a popular matching. However, there are simple instances where no popular matching exists. Here we consider the following natural extension to the above problem: associated with each item b belonging to B is a non-negative price cost(b), that is, for any item b, new copies of b can be added to the input graph by paying an amount of cost(b) per copy. When G does not admit a popular matching, the problem is to "augment" G at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of sqrt{n1}/2, where n1 is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of "constructing" a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length 2, the problem becomes NP-hard. On the other hand, when the number of copies of each item is "fixed", we show that the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in O(mn1) time, where m is the number of edges.

0 citations0 reviewsNo code linkedOpen access