Arrow Research search

Author name cluster

Ashlesha Hota

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

AAMAS Conference 2026 Conference Paper

Minimizing Envy and Maximizing Happiness in Graphical House Allocation

  • Anubhav Dhar
  • Ashlesha Hota
  • Palash Dey
  • Sudeshna Kolay

We study graphical house allocation, where agents are connected by a friendship graph and envy can arise only between neighboring agents. Each agent approves a subset of houses and envies a friend if she receives no approved house while the friend is allocated one she approves. We consider two problems: minimizing the number of envious agents, and, among such allocations, maximizing the number of agents receiving an approved house. We provide a detailed complexity analysis, showing that both problems are solvable in polynomial time when each agent approves at most one house, but become NP-hard when agents may approve two houses, establishing a tight tractability boundary. We further present exact algorithms under structural restrictions on the agent graph, including sparsity, small balanced separators, and bounded vertex cover.

PDF

AAMAS Conference 2026 Conference Paper

Universal Solvability for Robot Motion Planning on Graphs

  • Anubhav Dhar
  • Pranav Nyati
  • Tanishq Prasad
  • Ashlesha Hota
  • Sudeshna Kolay

Autonomousmulti-robotsystemsinmodernwarehousesoftenneed robots to be rearranged for efficient task execution. A key question is whether the underlying layout allows transformation between any two configurations without collisions. We model the layout as a graph𝐺(𝑉, 𝐸), with vertices as locations and edges as paths, and study the Universal Solvability of Robot Motion Planning on Graphs (USolR) problem: given𝐺 and 𝑝 robots, does𝐺 allow any configuration to be transformed into any other via valid moves? For this, we design a linear-time randomized algorithm with onesided error that always correctly identifies universally solvable graphs and may fail only on non-universally solvable instances; derandomization incurs a factor-𝑝 overhead, giving deterministic running times of 𝑂(𝑝(|𝑉| + |𝐸|)) for sparse and 𝑂(|𝑉| + |𝐸|) for dense graphs. Finally, we consider the Graph Edge Augmentation for Universal Solvability (EAUS) problem: given a connected graph𝐺 notuniversallysolvablefor𝑝 robots, canatmost𝛽 edgesbe added to make it universally solvable? We show an upper bound of 𝑝−2on𝛽 forgeneralgraphsandgiveexamplesrequiringΘ(𝑝) edge additions. WethenstudyGraphVertexandEdgeAugmentation forUniversalSolvability(VEAUS), where𝛼 verticesand𝛽 edges may be added, and provide lower bounds on these parameters.

PDF
v2026.09.13