Poster "approximation algorithms" Papers
24 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
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.
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.
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
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
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.
Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs
Slobodan Mitrovic, Theodore Pan
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