Cover Image

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Soma, Tasuku, Ye, Mingquan, Yoshida, Yuichi
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

Lipschitz Continuous Algorithms for Covering Problems
by: Kumabe, Soh, et al.
Published: (2023)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

Tolerant Testing for Unique Games
by: Yoshida, Yuichi
Published: (2026)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
by: Yoshida, Yuichi
Published: (2026)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
by: Yoshida, Yuichi
Published: (2026)

Testing Monotonicity of Real-Valued Functions on DAGs
by: Yoshida, Yuichi
Published: (2026)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

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

Pointwise Lipschitz Continuous Graph Algorithms
by: Liu, Quanquan C., et al.
Published: (2024)

Simple Algorithms for Stochastic Score Classification with Small Approximation Ratios
by: Plank, Benedikt M., et al.
Published: (2022)

Average sensitivity of the Knapsack Problem
by: Kumabe, Soh, et al.
Published: (2024)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
by: Chuzhoy, Julia, et al.
Published: (2024)

Approximate Bipartite $b$-Matching using Multiplicative Auction
by: Samineni, Bhargav, et al.
Published: (2024)

Algorithmic aspects of semistability of quiver representations
by: Iwamasa, Yuni, et al.
Published: (2024)

Efficient Kernelization Algorithm for Bipartite Graph Matching
by: Wu, Guang, et al.
Published: (2024)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time
by: Leung, Yui Hin Arvin
Published: (2025)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
by: Kempa, Dominik, et al.
Published: (2025)

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
by: Papadopoulos, Kleitos
Published: (2025)

Courcelle's Theorem for Lipschitz Continuity
by: Gima, Tatsuya, et al.
Published: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
by: Chaplick, Steven, et al.
Published: (2024)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling
by: Zhao, Jingyang, et al.
Published: (2025)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
by: Kumar, Mithilesh, et al.
Published: (2024)

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
by: Holm, Jacob, et al.
Published: (2025)

An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
by: Papadopoulos, Kleitos
Published: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
by: Shibata, Hiroki, et al.
Published: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

Building a Balanced k-d Tree in O(kn log n) Time
by: Brown, Russell A.
Published: (2014)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Biclique Reconfiguration in Bipartite Graphs
by: Otachi, Yota, et al.
Published: (2026)

Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach
by: Ye, Xiaowei, et al.
Published: (2024)

Improved Approximation Ratios for the Shortest Common Superstring Problem with Reverse Complements
by: Yamano, Ryosuke, et al.
Published: (2026)

The Impact of Approximation on Algorithmic Progress
by: Li, Jeffery, et al.
Published: (2026)

Deterministic Online Bipartite Edge Coloring
by: Blikstad, Joakim, et al.
Published: (2024)