7 citations · 7 across the 7 of their papers we have counts for
14 papers
Fair Allocation under Conflict Constraints
Sarfaraz Equbal, Rohit Gurjar, Ayumi Igarashi +6
We study the fair allocation of indivisible items subject to conflict constraints. In this framework, the items are represented as the vertices of a graph, with edges corresponding…
Approximately Optimal Mechanism Design for Competing Sellers
Brendan Lucier, Raghuvansh R. Saxena
Two sellers compete to sell identical products to a single buyer. Each seller chooses an arbitrary mechanism, possibly involving lotteries, to sell their product. The utility-maxim…
Streaming Algorithms via Local Algorithms for Maximum Directed Cut
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of Buchbinder et al…
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We give an -space single-pass -approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on …
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
We consider prophet inequalities subject to feasibility constraints that are the intersection of matroids. The best-known algorithms achieve a -approximation, even when r…
Streaming complexity of CSPs with randomly ordered constraints
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan +1
We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely $\…