:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Gupta, Anupam, Lee, Euiwoong, Li, Jason, Mucha, Marcin, Newman, Heather, Sarkar, Sherry
Format:	Preprint
Published:	2021
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2111.09290
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dual Charging for Half-Integral TSP
by: Klein, Nathan, et al.
Published: (2025)

Improved Algorithms for Fair Matroid Submodular Maximization
by: Mahabadi, Sepideh, et al.
Published: (2026)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Max Cut with Small-Dimensional SDP Solutions
by: Chang, Hsien-Chih, et al.
Published: (2026)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Approximating Small Sparse Cuts
by: Anand, Aditya, et al.
Published: (2024)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
by: Anand, Aditya, et al.
Published: (2025)

Facility Location on High-dimensional Euclidean Spaces
by: Lee, Euiwoong, et al.
Published: (2025)

Separating $k$-Median from the Supplier Version
by: Anand, Aditya, et al.
Published: (2024)

Understanding the Cluster LP for Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Unbreakable Decomposition in Close-to-Linear Time
by: Anand, Aditya, et al.
Published: (2024)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
by: Lee, Dahoon, et al.
Published: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
by: Khanna, Sanjeev, et al.
Published: (2026)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

Combinatorial Optimization using Comparison Oracles
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Online Metric TSP
by: Bertram, Christian
Published: (2025)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

The Online Submodular Cover Problem
by: Gupta, Anupam, et al.
Published: (2025)

Steiner Forest: A Simplified Better-Than-2 Approximation
by: Gupta, Anupam, et al.
Published: (2025)

Fully-Dynamic Submodular Cover with Bounded Recourse
by: Gupta, Anupam, et al.
Published: (2020)

Dynamic Matroids: Base Packing and Covering
by: de Vos, Tijn, et al.
Published: (2025)

Sample-Based Matroid Prophet Inequalities
by: Fu, Hu, et al.
Published: (2024)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

Efficiently Coloring the Intersection of a General Matroid and Partition Matroids
by: Arndt, Stephen, et al.
Published: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Online Steiner Forest with Recourse
by: Long, Yaowei, et al.
Published: (2026)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
by: Buchbinder, Niv, et al.
Published: (2026)

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
by: Hellerstein, Lisa, et al.
Published: (2026)

Approximating Prize-Collecting Variants of TSP
by: Alimi, Morteza, et al.
Published: (2024)

4/3-Approximation of Graphic TSP
by: Çivril, Ali
Published: (2023)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

Clustering with Non-adaptive Subset Queries
by: Black, Hadley, et al.
Published: (2024)

Submodular Maximization Subject to Uniform and Partition Matroids: From Theory to Practical Applications and Distributed Solutions
by: Kia, Solmaz S.
Published: (2025)