The House Allocation problem is about dividing a set of houses among a group of people so that everyone gets exactly one house. Each person has his own preference over the set of houses. Under an allocation, Alice is said to be envious of Bob if she likes Bob's house better than hers. The problem is then to find an allocation that minimizes the amount of envy experienced by the people. This problem is a generalization of several real-world problems, including public housing allocation, organ allocation, job allocation, college dormitory allocation, etc.
In this work, we consider the house allocation problem where people's preferences are modeled as either strict rankings or binary approvals. We investigate three different objectives: 1) minimizing the number of people who are envious, 2) minimizing the maximum amount of envy experienced by anyone, and, 3) minimizing the total amount of envy experienced by everyone. In the first objective, the problem is known to be hard even when the preferences are binary. We show that the problem remains hard even with further restrictions (e.g. every agent approves a bounded number of houses or every house is approved by a constant number of agents). For a structured class of input (i.e. extremal valuations), we give efficient algorithms for all three problems. We also suggest practical approaches for these problems using ILP formulations, thereby establishing tractability when the underlying parameter is the number of agents (or houses).
Given a set of n keys, we can trivially search for any key in O(n) time. Data structures such as Binary Search Trees(BSTs) store the n keys in a fashion so that we can search any key in O(logn) time (assuming the tree is balanced). Therefore, given a sequence of n searches, we can perform them in O(nlogn) time using balanced binary search trees, such as AVL trees.
Two binary search trees, Splay and Greedy, are conjectured to search any sequence of n keys in O(OPT) time, where OPT is the optimum time to search the sequence. Our recent work shows that Greedy takes almost O(n) time if the searched sequence has some structure. Particularly, we show that the Preorder, Deque, and Split sequences take almost O(n) time, and the Postorder sequence takes O(n) time for Greedy. The idea behind all these results is to partition (based on the input structures) Greedy into several simpler-to-analyze subsets for which classical forbidden submatrix bounds can be used.
This paper appeared in SODA 2023.
We will look at two ways of computing polynomials: one as expressions over ring operations and another as a product of 2 by 2 matrices, where each entry is a variable or a constant. We will explore what approximate computation is and the known result that any polynomial with a small formula (expression) can be approximately computed as a multiplication of a small number of 2 by 2 matrices (over fields of characteristic not equal to 2). We will discuss our attempt to generalise this to fields of characteristic 2 and discuss some open questions in that direction. This is joint work with Pranjal Dutta, Balagopal Komarath, Dhara Thakkar, and Harshil Mittal.
An orientation of an undirected graph G is an assignment of exactly one direction to each of the edges of G. An orientation of a graph G is called a strong orientation if from each vertex there is a directed path to every other vertex. The oriented diameter of a graph G is the smallest diameter among all the strong orientations of G. The oriented diameter of a family of graphs F is the maximum oriented diameter among all the graphs in F.
In 1978, Chvátal and Thomassen gave a lower bound of (1/2)d²+d and an upper bound of 2d²+2d for the oriented diameter of the family of 2-edge connected graphs with diameter d. In 1985, Chung, Garey, and Tarjan gave an upper bound of 8d²+8d for the oriented diameter of the family of 2-edge connected mixed multigraphs with diameter d. There has been extensive research on the oriented diameter of 2-edge connected graphs with a diameter less than 5 as well. In this presentation, a concise summary is provided about these topics along with the most recent findings in this field.