My research papers are listed below.
- An FPTAS for Connectivity Interdiction (with Nidia Obscura Acosta and Sorrachai Yingchareonthawornchai) IPCO 2024
- Robust Sparsification for Matroid Intersection with Applications (with François Sellier) SODA 2024
- FPT-Algorithms for the $\ell$-Matchoid Problem with a Coverage Objective (with Justin Ward) SIDMA
- Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver (with
Parinya Chalermsook, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert and Sorrachai Yingchareonthawornchai) ICALP 2022
- Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms (with
François Sellier) SWAT 2022
- Maximum Weight b-Matchings in Random-Order Streams (with
François Sellier) ESA 2022
- Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint (with
François Sellier) APPROX 2021
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths (with
Mathieu Mari, Claire Mathieu, Kevin Schwior, and Jens Vygen) SIDMA
- Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model (with
Naonori Kakimura, Simon Mauras, and Yuichi Yoshida) SIDMA
- Approximating Maximum Integral Multiflows on Bounded Genus Graphs (with
Mathieu Mari, Claire Mathieu, and Jens Vygen) ICALP 2021
- Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints (with
Theophile Thiery, and Justin Ward) APPROX 2020
- Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint (with
Mathieu Mari, Claire Mathieu, Joseph S.B. Mitchell, and Nabil Mustafa) APPROX 2019
- Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint (with Naonori Kakimura
) WADS 2019
- Distributed Exact Weighted All-Pairs Shortest Paths in O~(n^{5/4}) Rounds (with
Danupon Nanongkai and Thatchaphol Saranurak) FOCS 2017
- Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint (with
Naonori Kakimura and Yuichi Yoshida) APPROX 2017
- Popularity, Mixed Matchings, and Self-duality (with
Kavitha Telikepalli) SODA 2017
- Priority Mutual Exclusion: Specification and Algorithm (with
Prasad Jayanti) DISC 2016
- A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges (with Sebastian Ott
) ESA 2016
- Exact and Approximation Algorithms for Weighted Matroid Intersection (with Naonori Kakimura and Naoyuki Kamiyama) SODA 2016
- A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties (with Kazuo Iwama,
Shuichi Miyazaki, and
Hiroki Yanagisawa) APPROX 2015
Unfortunately, there is a mistake in the proof of Lemma 16 in this paper. We are unable to
fix the error. Hence the main positive result of this work, namely, the 1.25-approximation
algorithm, does not work.
- Coordinating Oligopolistic Players in Unrelated Machine Scheduling (with Fidaa Abed) Theoretical Computer Science
- Popular Matchings with One-sided Ties (with Ágnes Cseh and Kavitha Telikepalli) ICALP 2015
- Maintaining Near-Popular Matchings (with Sayan Bhattacharya, Martin Hoefer,
Lisa Wagner, and
Kavitha Telikepalli) ICALP 2015
- A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State (with Antonios Antoniadis and Sebastian Ott) SODA 2015
- Optimal Coordination Mechanisms for Multi-Job Scheduling Games (with Fidaa Abed and José Correa) ESA 2014
- New Results for Non-Preemptive Speed Scaling (with Sebastian Ott) MFCS 2014
- An Improved Approximation Algorithm for the Stable Marriage Problem with One-sided Ties (with Kavitha Telikepalli) IPCO 2014
- How to Pack Your Items When You Have to Buy Your Knapsack (with Antonios Antoniadis, Sebastian Ott, and
José Verschae) MFCS 2013
- Preemptive Coordination Mechanisms for Unrelated Machines (with Fidaa Abed) ESA 2012
-
Non-preemptive Speed Scaling (with Antonios Antoniadis) SWAT 2012
-
Efficient Algorithms for Maximum Weight Matchings in General Graphs with Small Edge Weights (with Kavitha Telikepalli) SODA 2012
(the version here is significantly different from the conference version.)
-
Near-popular matchings in the Roommates problem (with Kavitha Telikepalli) ESA 2011
- Collusion in Atomic Splittable Routing Games ICALP 2011
- Popular Matchings in the Stable Marriage Problem (with Kavitha Telikepalli) ICALP 2011
- On Expressing Value Externalities in Position Auctions (with Florin Constantin, Malvika Rao, and David Parkes) AAAI 2011
- Parameterized Two-Player Nash Equilibrium (with
Danny Hermelin, Stefan Kratsch, and Magnus Wahlström) WG 2011
-
Group Mutual Exclusion in O(log n) RMR
(with Vibhor Bhatt) PODC 2010
- The Price of Collusion in Series-Parallel Networks
(with Umang Bhaskar and
Lisa Fleischer) IPCO 2010
- Classified
Stable Matching SODA 2010 (arXiv)
- Donation Center Location
Problem (with Zoya Svitkina) FSTTCS 2009
- Equilibria of Atomic Flow Games are not Unique (with Umang Bhaskar,
Lisa Fleischer, and
Darrell Hoy) SODA 2009
- Bounded Unpopularity
Matchings (with Kavitha Telikepalli,
Dimitris Michail, and
Meghana Nasre) SWAT 2008
-
Two's Company, Three's a Crowd: Stable Family and Threesome Roommates Problems
ESA 2007
-
Cheating to Get Better Roommates in a Random Stable Matching STACS 2007
- Cheating by Men in the Gale-Shapley Stable Matching Algorithm ESA 2006
My collaborators: I write down their names as a recognition of my gratitude. Thanks
so much for the happy time we spent together and the many things you have taught me over the
years.
Fidaa Abed,
Antonios Antoniadis, Chrisil Arackaparambil, Umang Bhaskar, Sayan Bhattacharya,
Vibhor Bhatt,
Amit Chakrabarti,
Florin Constantin, José Correa,
Ágnes Cseh,
Lisa Fleischer, Danny Hermelin, Martin Hoefer,
Darrell Hoy, Kazuo Iwama, Naonori Kakimura, Naoyuki Kamiyama,
Ming-Yang Kao, Telikepalli Kavitha, Stephan Kratsch, Xiang-Yang Li, Kurt Mehlhorn,
Shuichi Miyazaki, Danupon Nanongkai, Meghana Nasre,
Dimitris Michail, Sebastian Ott,
David Parkes, Malvika Rao, Thatchaphol Saranurak, Zoya Svitkina, Yih-Kuen Tsay, José Verschae,
Lisa Wagner, Magnus Wahlström, Hiroki Yanagisawa, Yuichi Yoshida.