"approximation algorithms" Papers
36 papers found
Conference
Approximation algorithms for combinatorial optimization with predictions
Antonios Antoniadis, Marek Elias, Adam Polak et al.
A Single-Swap Local Search Algorithm for k-Means of Lines
Ting Liang, Xiaoliang Wu, Junyu Huang et al.
A Unified Approach to Submodular Maximization Under Noise
Kshipra Bhawalkar, Yang Cai, Zhe Feng et al.
Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio
Yang Cao, Xiaoyu Li, Zhao Song et al.
Fair Clustering in the Sliding Window Model
Vincent Cohen-Addad, Shaofeng Jiang, Qiaoyuan Yang et al.
Improved Algorithms for Fair Matroid Submodular Maximization
Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski
Improved Approximation Algorithms for $k$-Submodular Maximization via Multilinear Extension
Huanjian Zhou, Lingxiao Huang, Baoxiang Wang
Improved Maximin Share Approximations for Chores by Bin Packing
Jugal Garg, Xin Huang, Erel Segal-Halevi
Learning-Augmented Streaming Algorithms for Correlation Clustering
Yinhao Dong, Shan Jiang, Shi Li et al.
Near-optimal Active Regression of Single-Index Models
Yi Li, Wai Ming Tai
New Algorithms for the Learning-Augmented k-means Problem
Junyu Huang, Qilong Feng, Ziyun Huang et al.
New Parallel and Streaming Algorithms for Directed Densest Subgraph
Slobodan Mitrovic, Theodore Pan, Mahdi Qaempanah et al.
Proportionally Fair Makespan Approximation
Michal Feldman, Jugal Garg, Vishnu V. Narayan et al.
Proportionally Fair Matching via Randomized Rounding
Sharmila Duppala, Nathaniel Grammel, Juan Luque et al.
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
Christopher Musco, R. Teal Witter
Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
Shihong Song, Guanlin Mo, Hu Ding
Simple and Optimal Sublinear Algorithms for Mean Estimation
Beatrice Bertolotti, Matteo Russo, Chris Schwiegelshohn et al.
Stable Matching with Ties: Approximation Ratios and Learning
Shiyun Lin, Simon Mauras, Nadav Merlis et al.
Streaming Algorithms For $\ell_p$ Flows and $\ell_p$ Regression
Amit Chakrabarti, Jeffrey Jiang, David Woodruff et al.
Unifying Proportional Fairness in Centroid and Non-Centroid Clustering
Benjamin Cookson, Nisarg Shah, Ziqi Yu
A Dynamic Algorithm for Weighted Submodular Cover Problem
Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi et al.
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar
Approximate Integer Solution Counts over Linear Arithmetic Constraints
Cunjing Ge
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems
Hao Tian, Sourav Medya, Wei Ye
Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
Vicente Balmaseda, Ying Xu, Yixin Cao et al.
Consistent Submodular Maximization
PAUL DUETTING, Federico Fusco, Silvio Lattanzi et al.
Cost Minimization for Equilibrium Transition
Haoqiang Huang, Zihe Wang, Zhide Wei et al.
Dynamic Correlation Clustering in Sublinear Update Time
Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori et al.
Dynamic Facility Location in High Dimensional Euclidean Spaces
Sayan Bhattacharya, Gramoz Goranci, Shaofeng Jiang et al.
Envy-Free House Allocation under Uncertain Preferences
Haris Aziz, Isaiah Iliffe, Bo Li et al.
Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs
Slobodan Mitrovic, Theodore Pan
Improved Metric Distortion via Threshold Approvals
Elliot Anshelevich, Aris Filos-Ratsikas, Christopher Jerrett et al.
Near-Linear Time Approximation Algorithms for k-means with Outliers
Junyu Huang, Qilong Feng, Ziyun Huang et al.
Optimally Improving Cooperative Learning in a Social Setting
Shahrzad Haddadan, Cheng Xin, Jie Gao
Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
Evripidis Bampis, Bruno Escoffier, Michalis Xefteris