3 Search Results for "Gangam, Rohith Reddy"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.32
Fair Rent Division: New Budget and Rent Constraints

Authors: Rohith Reddy Gangam, Shayan Taherijam, and Vijay V. Vazirani

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the classical rent division problem, where n agents must allocate n indivisible rooms and split a fixed total rent R. The goal is to compute an envy-free (EF) allocation, where no agent prefers another agent’s room and rent to their own. This problem has been extensively studied under standard assumptions, where efficient algorithms for computing EF allocations are known. We extend this framework by introducing two practically motivated constraints: (i) lower and upper bounds on room rents, and (ii) room-specific budget for agents. We develop efficient combinatorial algorithms that either compute a feasible EF allocation or certify infeasibility. We further design algorithms to optimize over EF allocations using natural fairness objectives such as maximin utility, leximin utility, and minimum utility spread. Our approach unifies both constraint types within a single algorithmic framework, advancing the applicability of fair division methods in real-world platforms such as Spliddit.
Cite as

Rohith Reddy Gangam, Shayan Taherijam, and Vijay V. Vazirani. Fair Rent Division: New Budget and Rent Constraints. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gangam_et_al:LIPIcs.FSTTCS.2025.32,
  author =	{Gangam, Rohith Reddy and Taherijam, Shayan and Vazirani, Vijay V.},
  title =	{{Fair Rent Division: New Budget and Rent Constraints}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.32},
  URN =		{urn:nbn:de:0030-drops-251136},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.32},
  annote =	{Keywords: Rent Division, Envy‑Free, Fair Division}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.11
Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure

Authors: Mark de Berg, Andrés López Martínez, and Frits Spieksma

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We generalize the polynomial-time solvability of k-Diverse Minimum s-t Cuts (De Berg et al., ISAAC'23) to a wider class of combinatorial problems whose solution sets have a distributive lattice structure. We identify three structural conditions that, when met by a problem, ensure that a k-sized multiset of maximally-diverse solutions - measured by the sum of pairwise Hamming distances - can be found in polynomial time. We apply this framework to obtain polynomial-time algorithms for finding diverse minimum s-t cuts, diverse stable matchings, and diverse market-clearing price vectors. Moreover, we show that the framework extends to two other natural measures of diversity. Lastly, we present a simpler algorithmic framework for finding a largest set of pairwise disjoint solutions in problems that meet these structural conditions.
Cite as

Mark de Berg, Andrés López Martínez, and Frits Spieksma. Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2025.11,
  author =	{de Berg, Mark and L\'{o}pez Mart{\'\i}nez, Andr\'{e}s and Spieksma, Frits},
  title =	{{Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.11},
  URN =		{urn:nbn:de:0030-drops-249197},
  doi =		{10.4230/LIPIcs.ISAAC.2025.11},
  annote =	{Keywords: Diversity, Lattice Theory, Submodular Function Minimization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.19
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications

Authors: Rohith Reddy Gangam, Tung Mai, Nitya Raju, and Vijay V. Vazirani

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Recently [Mai and Vazirani, 2018] identified and initiated work on a new problem, namely understanding structural relationships between the lattices of solutions of two "nearby" instances of stable matching. They also gave an application of their work to finding a robust stable matching. However, the types of changes they allowed in going from instance A to B were very restricted, namely any one agent executes an upward shift. In this paper, we allow any one agent to permute its preference list arbitrarily. Let M_A and M_B be the sets of stable matchings of the resulting pair of instances A and B, and let ℒ_A and ℒ_B be the corresponding lattices of stable matchings. We prove that the matchings in M_A ∩ M_B form a sublattice of both ℒ_A and ℒ_B and those in M_A ⧵ M_B form a join semi-sublattice. These properties enable us to obtain a polynomial time algorithm for not only finding a stable matching in M_A ∩ M_B, but also for obtaining the partial order, as promised by Birkhoff’s Representation Theorem [Birkhoff, 1937]. As a result, we can generate all matchings in this sublattice. Our algorithm also helps solve a version of the robust stable matching problem. We discuss another potential application, namely obtaining new insights into the incentive compatibility properties of the Gale-Shapley Deferred Acceptance Algorithm.
Cite as

Rohith Reddy Gangam, Tung Mai, Nitya Raju, and Vijay V. Vazirani. A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gangam_et_al:LIPIcs.FSTTCS.2022.19,
  author =	{Gangam, Rohith Reddy and Mai, Tung and Raju, Nitya and Vazirani, Vijay V.},
  title =	{{A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.19},
  URN =		{urn:nbn:de:0030-drops-174114},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.19},
  annote =	{Keywords: stable matching, robust solutions, finite distributive lattice, Birkhoff’s Representation Theorem}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2022

  • Refine by Author
  • 2 Gangam, Rohith Reddy
  • 2 Vazirani, Vijay V.
  • 1 López Martínez, Andrés
  • 1 Mai, Tung
  • 1 Raju, Nitya
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Birkhoff’s Representation Theorem
  • 1 Diversity
  • 1 Envy‑Free
  • 1 Fair Division
  • 1 Lattice Theory
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact