Cover Image

Hardness and Approximation Algorithms for Balanced Districting Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dharangutte, Prathamesh, Gao, Jie, Huang, Shang-En, Yu, Fang-Yi
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Packing Compact Subgraphs with Applications to Districting
by: Chen, Ho-Lin, et al.
Published: (2026)

The Price of Privacy For Approximating Max-CSP
by: Dharangutte, Prathamesh, et al.
Published: (2026)

Learning-augmented Maximum Independent Set
by: Braverman, Vladimir, et al.
Published: (2024)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
by: Braverman, Vladimir, et al.
Published: (2024)

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
by: Albers, Susanne, et al.
Published: (2025)

Relative Error Fair Clustering in the Weak-Strong Oracle Model
by: Braverman, Vladimir, et al.
Published: (2025)

Automating the Search for Small Hard Examples to Approximation Algorithms
by: Sharma, Eklavya
Published: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
by: Madani, Amirali, et al.
Published: (2025)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
by: Yamano, Ryosuke, et al.
Published: (2026)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
by: Lokshtanov, Daniel, et al.
Published: (2024)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
by: Chen, Yong, et al.
Published: (2025)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
by: Zhao, Jingyang, et al.
Published: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

Cactus Representation of Minimum Cuts: Derandomize and Speed up
by: He, Zhongtian, et al.
Published: (2024)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

Approximations and Hardness of Packing Partially Ordered Items
by: Doron-Arad, Ilan, et al.
Published: (2024)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Optimal 4-Approximation for the Correlated Pandora's Problem
by: Bansal, Nikhil, et al.
Published: (2025)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
by: Agarwal, Arpit, et al.
Published: (2024)

Balanced Partitioning for Optimizing Big Graph Computation: Complexities and Approximation Algorithms
by: Ning, Baoling, et al.
Published: (2024)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
by: Esmer, Barış Can, et al.
Published: (2024)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
by: Bucić, Matija, et al.
Published: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

New Algorithms and Hardness Results for Connected Clustering
by: Eube, Jan, et al.
Published: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

A Reduction-based Algorithm for the Clique Interdiction Problem
by: Zhu, Chenghao, et al.
Published: (2025)

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
by: Rui, Xiaobin, et al.
Published: (2025)

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
by: Berg, Magnus
Published: (2024)

On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms
by: Schlöter, Jens
Published: (2025)