| |
|
Publications
What is now proved was once only imagined. --William Blake
This page presents my published papers (authors with * are sorted by alphabet order of their last names).
- Crossing number in slightly superexponential time.
Daniel Lokshtanov*, Fahad Panolan*, Saket Saurabh*, Roohani Sharma*, Jie Xue*, Meirav Zehavi*.
Accepted to the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.
- PTASes for Euclidean TSP with unit disk and unit square neighborhoods.
Sayan Bandyapadhyay*, Katie Clinch*, William Lochet*, Daniel Lokshtanov*, Saket Saurabh*, Jie Xue*.
Accepted to the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.
- Parameterized approximation for capacitated d-hitting set with hard capacities.
Daniel Lokshtanov*, Abhishek Sahu*, Saket Saurabh*, Vaishali Surianarayanan*, Jie Xue*.
Accepted to the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.
- Bipartizing (pseudo-)disk graphs: approximation with a ratio better than 3.
Daniel Lokshtanov*, Fahad Panolan*, Saket Saurabh*, Jie Xue*, Meirav Zehavi*.
In the 27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2024.
- Efficient approximation of hypertree width.
Vika Korchemna*, Daniel Lokshtanov*, Saket Saurabh*, Vaishali Surianarayanan*, Jie Xue*.
In the 65th IEEE Symposium on Foundations of Computer Science (FOCS), 2024.
- Sparse outerstring graphs have logarithmic treewidth.
Shinwoo An*, Eunjin Oh*, Jie Xue*.
In the 32th Annual European Symposium on Algorithms (ESA), 2024.
- An O(nlogn)-time approximation scheme for geometric many-to-many matching.
Sayan Bandyapadhyay*, Jie Xue*.
In the 40th International Symposium on Computational Geometry (SoCG), 2024.
Winner of the Best Paper Award.
- Algorithms for halfplane coverage and related problems.
Haitao Wang*, Jie Xue*.
In the 40th International Symposium on Computational Geometry (SoCG), 2024.
- Optimal algorithm for the planar two-center problem.
Kyungjin Cho*, Eunjin Oh*, Haitao Wang*, Jie Xue*.
In the 40th International Symposium on Computational Geometry (SoCG), 2024.
Extended version in TheoretiCS (invited), 2024.
- A 1.9999-approximation algorithm for vertex cover on string graphs.
Daniel Lokshtanov*, Fahad Panolan*, Saket Saurabh*, Jie Xue*, Meirav Zehavi*.
In the 40th International Symposium on Computational Geometry (SoCG), 2024.
- Enclosing points with geometric objects.
Timothy M. Chan*, Qizheng He*, Jie Xue*.
In the 40th International Symposium on Computational Geometry (SoCG), 2024.
- Euclidean bottleneck Steiner tree is fixed-parameter tractable.
Sayan Bandyapadhyay*, William Lochet*, Daniel Lokshtanov*, Saket Saurabh*, Jie Xue*.
In the 35th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.
- Fault tolerance in Euclidean committee selection.
Chinmay Sonar*, Subhash Suri*, Jie Xue*.
In the 31th Annual European Symposium on Algorithms (ESA), 2023.
- Minimum-membership geometric set cover, revisited.
Sayan Bandyapadhyay*, William Lochet*, Saket Saurabh*, Jie Xue*.
In the 39th International Symposium on Computational Geometry (SoCG), 2023.
- Clustering what matters: optimal approximation for clustering with outliers.
Akanksha Agrawal*, Tanmay Inamdar*, Saket Saurabh*, Jie Xue*.
In the 37th AAAI conference on Artificial Intelligence (AAAI), 2023.
Selected as AAAI Distinguished Paper.
Extended version in Journal of Artificial Intelligence Research, 2023.
- A framework for approximation schemes on disk graphs.
Daniel Lokshtanov*, Fahad Panolan*, Saket Saurabh*, Jie Xue*, Meirav Zehavi*.
In the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.
- ShadowAQP: efficient approximate group-by and join query via attribute-oriented sample size allocation and data generation.
Rong Gu, Han Li, Haipeng Dai, Wenjie Huang, Jie Xue, Meng Li, Jiaqi Zheng, Haoran Cai, Yihua Huang, Guihai Chen.
In the 49th International Conference on Very Large Data Bases (VLDB), 2023.
- Multiwinner elections under minimax Chamberlin-Courant rule in Euclidean space.
Chinmay Sonar*, Subhash Suri*, Jie Xue*.
In the 31th International Joint Conference on Artificial Intelligence (IJCAI), 2022.
- True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs.
Sayan Bandyapadhyay*, William Lochet*, Daniel Lokshtanov*, Saket Saurabh*, Jie Xue*.
In the 38th International Symposium on Computational Geometry (SoCG), 2022.
Extended version in ACM Transactions on Algorithms, 2024.
- Point separation and obstacle removal by finding and hitting odd cycles.
Neeraj Kumar*, Daniel Lokshtanov*, Saket Saurabh*, Subhash Suri*, Jie Xue*.
In the 38th International Symposium on Computational Geometry (SoCG), 2022.
Invited to SoCG special issue (regretfully declined).
- Subexponential parameterized algorithms for cut and cycle hitting problems on H-minor-free graphs.
Sayan Bandyapadhyay*, William Lochet*, Daniel Lokshtanov*, Saket Saurabh*, Jie Xue*.
In the 33th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.
- Dynamic geometric set cover, revisited.
Timothy M. Chan*, Qizheng He*, Subhash Suri*, Jie Xue*.
In the 33th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.
- Subexponential parameterized algorithms on disk graphs.
Daniel Lokshtanov*, Fahad Panolan*, Saket Saurabh*, Jie Xue*, Meirav Zehavi*.
In the 33th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.
- An ETH-tight algorithm for multi-team formation.
Daniel Lokshtanov*, Saket Saurabh*, Subhash Suri*, Jie Xue*.
In the 41st Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2021.
- Efficient algorithms for least square piecewise polynomial regression.
Daniel Lokshtanov*, Subhash Suri*, Jie Xue*.
In the 29th Annual European Symposium on Algorithms (ESA), 2021.
- Intuitive searching: an approach to search the decision policy of a Blackjack agent.
Zhenyu Pan, Jie Xue, Tingjian Ge.
In the 6th International Congress on Information and Communication Technology (ICICT), 2021.
- Fair covering of points by balls.
Daniel Lokshtanov*, Subhash Suri*, Chinmay Sonar*, Jie Xue*.
In the 32th Canadian Conference on Computational Geometry (CCCG), 2020.
- Dynamic geometric set cover and hitting set.
Pankaj K. Agarwal*, Hsien-Chih Chang*, Subhash Suri*, Allen Xiao*, Jie Xue*.
In the 36th International Symposium on Computational Geometry (SoCG), 2020.
Invited to SoCG special issue (regretfully declined).
Extended version in ACM Transactions on Algorithms, 2022.
- Improved algorithms for the bichromatic two-center problem for pairs of points.
Haitao Wang*, Jie Xue*.
In the 16th Algorithms and Data Structures Symposium (WADS), 2019.
Extended version in Computational Geometry: Theory and Applications, 2022.
- Range closest-pair in higher dimensions.
Timothy M. Chan*, Rahul Saladi*, Jie Xue*.
In the 16th Algorithms and Data Structures Symposium (WADS), 2019.
Extended version in Computational Geometry: Theory and Applications (WADS special issue), 2020.
- Searching for the closest-pair in a query translate.
Jie Xue, Yuan Li, Rahul Saladi, Ravi Janardan.
In the 35th International Symposium on Computational Geometry (SoCG), 2019.
Extended version in Journal of Computational Geometry (SoCG speicial issue), 2020.
- Near-optimal algorithms for shortest paths in weighted unit-disk graphs.
Haitao Wang*, Jie Xue*.
In the 35th International Symposium on Computational Geometry (SoCG), 2019.
Extended version in Discrete & Computational Geometry (SoCG speicial issue), 2020.
- Colored range closest-pair problem under general distance functions.
Jie Xue.
In the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.
- Scalable computational geometry in MapReduce.
Ahmed Eldawy, Yuan Li, Jie Xue, Nadezda Weber, Mohamed F. Mokbel, Ravi Janardan.
In the VLDB Journal, 2019.
- Approximate range closest-pair queries.
Jie Xue, Yuan Li, Ravi Janardan.
In the 30th Canadian Conference on Computational Geometry (CCCG), 2018.
Extended version in Computational Geometry: Theory and Applications (CCCG special issue), 2020.
- New bounds for range closest-pair problems.
Jie Xue, Yuan Li, Rahul Saladi, Ravi Janardan.
In the 34th International Symposium on Computational Geometry (SoCG), 2018.
Extended version in Discrete & Computational Geometry, 2022.
- Revealing the relations between learning behaviors and examination scores via a prediction system.
Zhenyu Pan, Jie Xue, Yang Gao, Honghao Wang, Guanling Chen.
In the 2nd International Conference on Computer Science and Artificial Intelligence (CSAI), 2018.
- On the expected diameter, width, and complexity of a stochastic convex-hull.
Jie Xue, Yuan Li, Ravi Janardan.
In the 15th Algorithms and Data Structures Symposium (WADS), 2017.
Extended version in Computational Geometry: Theory and Applications, 2019.
- Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces.
Jie Xue, Yuan Li.
In the 15th Algorithms and Data Structures Symposium (WADS), 2017.
- On the arrangement of stochastic lines in R^2.
Yuan Li, Jie Xue, Akash Agrawal, Ravi Janardan.
In Journal of Discrete Algorithms, 2017.
- The most-likely skyline problem for stochastic points.
Akash Agrawal, Yuan Li, Jie Xue, Ravi Janardan.
In the 29th Canadian Conference on Computational Geometry (CCCG), 2017.
Extended version in Computational Geometry: Theory and Applications (CCCG special issue), 2018.
- On the separability of stochastic geometric objects, with applications.
Jie Xue, Yuan Li, Ravi Janardan.
In the 32nd International Symposium on Computational Geometry (SoCG), 2016.
Extended version in Computational Geometry: Theory and Applications, 2018.
- On dominance-free samples of a (colored) stochastic dataset.
Jie Xue, Yuan Li.
|
