Buchumschlag

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Adriaens, Florian, Bengali, Vedangi, Kumpulainen, Iiro, Tatti, Nikolaj, Veldt, Nate
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity 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

The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards
von: Bengali, Vedangi, et al.
Veröffentlicht: (2025)

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
von: Bengali, Vedangi, et al.
Veröffentlicht: (2024)

Max-Min Diversification with Asymmetric Distances
von: Kumpulainen, Iiro, et al.
Veröffentlicht: (2025)

Finding coherent node groups in directed graphs
von: Kumpulainen, Iiro, et al.
Veröffentlicht: (2023)

Dense Subgraph Discovery Meets Strong Triadic Closure
von: Arachchi, Chamalee Wickrama, et al.
Veröffentlicht: (2025)

Fair Diversity Maximization with Few Representatives
von: Adriaens, Florian, et al.
Veröffentlicht: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

Minimum Stable Cut and Treewidth
von: Lampis, Michael
Veröffentlicht: (2021)

Multilayer Correlation Clustering
von: Miyauchi, Atsushi, et al.
Veröffentlicht: (2024)

Improved Hardness of Approximation for Geometric Bin Packing
von: Ray, Arka, et al.
Veröffentlicht: (2023)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

An Improved Combinatorial Algorithm for Edge-Colored Clustering in Hypergraphs
von: Han, Seongjune, et al.
Veröffentlicht: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Approximating splits for decision trees quickly in sparse data streams
von: Tatti, Nikolaj
Veröffentlicht: (2026)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
von: Kenig, Batya
Veröffentlicht: (2025)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
von: Stoian, Mihail
Veröffentlicht: (2024)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
von: Bilò, Davide, et al.
Veröffentlicht: (2025)

The Complexity of Counting Small Sub-Hypergraphs
von: Bressan, Marco, et al.
Veröffentlicht: (2025)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
von: Bhaskar, Umang, et al.
Veröffentlicht: (2025)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
von: Adriaens, Florian, et al.
Veröffentlicht: (2026)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
von: Gribanov, Dmitry, et al.
Veröffentlicht: (2022)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
von: Kurita, Kazuhiro, et al.
Veröffentlicht: (2025)

Parameterized Critical Node Cut Revisited
von: Knop, Dušan, et al.
Veröffentlicht: (2025)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
von: Upirvitskiy, Aleksey, et al.
Veröffentlicht: (2026)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Hardness of Dynamic Core and Truss Decompositions
von: Couto, Yan S., et al.
Veröffentlicht: (2025)

Algorithms and Hardness for Estimating Statistical Similarity
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Sampling Permutations with Cell Probes is Hard
von: Alekseev, Yaroslav, et al.
Veröffentlicht: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
von: Frei, Fabian, et al.
Veröffentlicht: (2024)

Hardness Results on Characteristics for Elastic-Degenerated Strings
von: Köppl, Dominik, et al.
Veröffentlicht: (2024)

k-SUM Hardness Implies Treewidth-SETH
von: Lampis, Michael
Veröffentlicht: (2025)