Buchumschlag

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Hwang, Samuel, Singer, Noah G., Velusamy, Santhoshini
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
von: Saxena, Raghuvansh R., et al.
Veröffentlicht: (2024)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
von: Velusamy, Santhoshini
Veröffentlicht: (2025)

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
von: Velusamy, Santhoshini, et al.
Veröffentlicht: (2025)

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
von: Cheng, Yu, et al.
Veröffentlicht: (2024)

Improved Upper Bounds for the Directed Flow-Cut Gap
von: Bodwin, Greg, et al.
Veröffentlicht: (2026)

Two New Upper Bounds for the Maximum k-plex Problem
von: Zheng, Jiongzhi, et al.
Veröffentlicht: (2023)

Sensitivity Lower Bounds for Approximaiton Algorithms
von: Fleming, Noah, et al.
Veröffentlicht: (2024)

New Algorithms and Lower Bounds for Streaming Tournaments
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

KD-Club: An Efficient Exact Algorithm with New Coloring-based Upper Bound for the Maximum k-Defective Clique Problem
von: Jin, Mingming, et al.
Veröffentlicht: (2023)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
von: Ahi, Mridul, et al.
Veröffentlicht: (2025)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
von: Huiberts, Sophie, et al.
Veröffentlicht: (2022)

Non-Signaling Locality Lower Bounds for Dominating Set
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
von: Manea, Florin, et al.
Veröffentlicht: (2024)

Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
von: Fioravantes, Foivos, et al.
Veröffentlicht: (2025)

Dynamic PageRank: Algorithms and Lower Bounds
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
von: Yoshida, Yuichi
Veröffentlicht: (2026)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
von: Funke, Daniel, et al.
Veröffentlicht: (2024)

Lower Bounds for Non-adaptive Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Latency Guarantees for Caching with Delayed Hits
von: Gurushankar, Keerthana, et al.
Veröffentlicht: (2025)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
von: Cervenjak, Philip, et al.
Veröffentlicht: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
von: Chitnis, Rajesh, et al.
Veröffentlicht: (2024)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
von: Atalig, Sunny, et al.
Veröffentlicht: (2024)

Adaptive BSTs for Single-Source and All-to-All Requests: Algorithms and Lower Bounds
von: Shiran, Maryam
Veröffentlicht: (2025)

A Lower Bound for the Max Entropy Algorithm for TSP
von: Jin, Billy, et al.
Veröffentlicht: (2023)

Deterministic Cache-Oblivious Funnelselect
von: Brodal, Gerth Stølting, et al.
Veröffentlicht: (2024)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Optimal Electrical Oblivious Routing on Expanders
von: Florescu, Cella, et al.
Veröffentlicht: (2024)

Optimal Non-Oblivious Open Addressing
von: Bender, Michael A., et al.
Veröffentlicht: (2025)

An approximation algorithm for Maximum DiCut vs. Cut
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
von: Bringmann, Karl, et al.
Veröffentlicht: (2026)

Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
von: Croquevielle, Luis Alberto, et al.
Veröffentlicht: (2026)