Zobrazeno 1 - 10
of 22
pro vyhledávání: '"Prajakta Nimbhorkar"'
Publikováno v:
Advances in Knowledge Discovery and Data Mining ISBN: 9783031333767
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::76f40fefcbb529690cf695ce96f08374
https://doi.org/10.1007/978-3-031-33377-4_18
https://doi.org/10.1007/978-3-031-33377-4_18
Publikováno v:
Journal of Combinatorial Optimization. 45
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0b6c278997b62451f7bdec13225c0f49
https://doi.org/10.1007/s10878-022-00963-x
https://doi.org/10.1007/s10878-022-00963-x
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, E), where each vertex in A U B specifies a strict preference ordering
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::af291f22a1d5edc597b6030731c94603
http://arxiv.org/abs/2206.12394
http://arxiv.org/abs/2206.12394
Publikováno v:
Datta, S, Limaye, N, Nimbhorkar, P, Thierauf, T & Wagner, F 2022, ' Planar Graph Isomorphism Is in Log-Space ', ACM Transactions on Computation Theory, vol. 14, no. 2, pp. 1-33 . https://doi.org/10.1145/3543686
IEEE Conference on Computational Complexity
IEEE Conference on Computational Complexity
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We b
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0f037a799bea4b34835f550acbfad138
https://pure.itu.dk/portal/da/publications/f73e611b-6bcc-40e5-8ede-12f8e2b754e1
https://pure.itu.dk/portal/da/publications/f73e611b-6bcc-40e5-8ede-12f8e2b754e1
Publikováno v:
Theoretical Computer Science. 767:73-82
Let G = ( A ∪ P , E ) be a bipartite graph where A denotes a set of applicants, 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 appli
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::628c6c7701f3a4c0e91c0e742638650e
https://doi.org/10.1016/j.tcs.2018.09.033
https://doi.org/10.1016/j.tcs.2018.09.033
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783030868376
WG
WG
We show that given a Stable Matching instance \(G\) as input, we can find a largest collection of pairwise edge-disjoint stable matchings of \(G\) in time linear in the input size. This extends two classical results: 1. The Gale-Shapley algorithm, wh
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::db98f3066d8d62a4227b3ed624e4348a
https://doi.org/10.1007/978-3-030-86838-3_7
https://doi.org/10.1007/978-3-030-86838-3_7
Publikováno v:
IJCAI
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 paper. Each platform specifies the group fairness constraints through
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::822b70bd541cff7490baddb1f80afa47
Publikováno v:
Algorithmic Game Theory ISBN: 9783030579791
SAGT
SAGT
We consider the problem of matchings under two-sided preferences in the presence of maximum as well as minimum quota requirements for the agents. When there are no minimum quotas, stability is the de-facto notion of optimality. In the presence of min
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5099f4ef72f2079bc7d19992d6a9e91d
https://doi.org/10.1007/978-3-030-57980-7_13
https://doi.org/10.1007/978-3-030-57980-7_13
Publikováno v:
Journal of Combinatorial Optimization. 37:523-545
We consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph $$G=(\mathcal {A}\cup \mathcal {P},E)$$ , where $$\mathcal {A}$$ denotes a set of applicants, $$\
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c0618f661f8b58f5688233642ca69deb
https://doi.org/10.1007/s10878-018-0348-9
https://doi.org/10.1007/s10878-018-0348-9
Publikováno v:
International Journal of Advances in Engineering Sciences and Applied Mathematics. 11:68-74
We study bounded-depth $$(\min ,+)$$ formulas computing the shortest path polynomial. For depth 2d with $$d \ge 2$$ , we obtain lower bounds parameterized by certain fan-in restrictions on $$+$$ gates except those at the bottom level. For depth 4, in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::22c68263641b7b074dff89b7595fdb6e
https://doi.org/10.1007/s12572-018-0229-6
https://doi.org/10.1007/s12572-018-0229-6