research
∙
05/03/2023
Algorithmic Theory of Qubit Routing
The qubit routing problem, also known as the swap minimization problem, ...
share
research
∙
04/28/2023
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
We prove that the computation of a combinatorial shortest path between t...
research
∙
10/21/2022
Rerouting Planar Curves and Disjoint Paths
In this paper, we consider a transformation of k disjoint paths in a gra...
research
∙
09/21/2022
On Reachable Assignments under Dichotomous Preferences
We consider the problem of determining whether a target item assignment ...
research
∙
07/06/2022
Reforming an Envy-Free Matching
We consider the problem of reforming an envy-free matching when each age...
research
∙
03/15/2022
Online Task Assignment Problems with Reusable Resources
We study online task assignment problem with reusable resources, motivat...
research
∙
10/22/2021
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
We initiate the study of k-edge-connected orientations of undirected gra...
research
∙
10/20/2021
Dynamic Bipartite Matching Market with Arrivals and Departures
In this paper, we study a matching market model on a bipartite network w...
research
∙
01/20/2021
Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions
The contextual combinatorial semi-bandit problem with linear payoff func...
research
∙
07/17/2020
Market Pricing for Matroid Rank Valuations
In this paper, we study the problem of maximizing social welfare in comb...
research
∙
02/13/2020
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
Maximizing a monotone submodular function under various constraints is a...
research
∙
11/20/2019
Online Spectral Approximation in Random Order Streams
This paper studies spectral approximation for a positive semidefinite ma...
research
∙
07/03/2019
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Motivated by adjacency in perfect matching polytopes, we study the short...
research
∙
06/14/2019
Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising
Computational advertising has been studied to design efficient marketing...
research
∙
04/17/2019
Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries
In the densest subgraph problem, given a weighted undirected graph G(V,E...
research
∙
06/06/2018
Causal Bandits with Propagating Inference
Bandit is a framework for designing sequential experiments. In each expe...
research
∙
02/17/2018
Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization
We consider maximizing a monotone submodular function under a cardinalit...
research
∙
02/07/2018
