Buchumschlag

Supermodular Maximization with Cardinality Constraints

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chen, Xujin, Hu, Xiaodong, Wang, Changjun, Ye, Qingjie
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Optimization and Control Discrete Mathematics Data Structures and Algorithms Combinatorics 05C85, 68W25, 90C27
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
von: Ammann, Sabrina C. L., et al.
Veröffentlicht: (2024)

Young domination on Hamming rectangles
von: Gravner, Janko, et al.
Veröffentlicht: (2025)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
von: Buchbinder, Niv, et al.
Veröffentlicht: (2024)

Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole
von: Haxell, Penny, et al.
Veröffentlicht: (2022)

Totally $Δ$-Modular Tree Decompositions of Graphic Matrices for Integer Programming
von: McFarland, Caleb
Veröffentlicht: (2026)

Loss Minimization for Electrical Flows over Spanning Trees on Grids
von: Ito, Takehiro, et al.
Veröffentlicht: (2024)

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
von: Nasre, Meghana, et al.
Veröffentlicht: (2023)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
von: Munaro, Andrea, et al.
Veröffentlicht: (2022)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
von: Liu, Bowen
Veröffentlicht: (2025)

Algorithms for the ferromagnetic Potts model on expanders
von: Carlson, Charlie, et al.
Veröffentlicht: (2022)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
von: Rockel-Wolff, Benjamin
Veröffentlicht: (2024)

A simple Path-based LP Relaxation for Directed Steiner Tree
von: Pashkovich, Kanstantsin, et al.
Veröffentlicht: (2026)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
von: Feldman, Moran, et al.
Veröffentlicht: (2026)

Symmetric Submodular Functions, Uncrossable Functions, and Structural Submodularity
von: Simmons, Miles, et al.
Veröffentlicht: (2025)

A $5$-Approximation Analysis for the Cover Small Cuts Problem
von: Simmons, Miles, et al.
Veröffentlicht: (2026)

Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity
von: Bansal, Ishan, et al.
Veröffentlicht: (2024)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
von: Heimann, Sophia, et al.
Veröffentlicht: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
von: Hougardy, Stefan, et al.
Veröffentlicht: (2024)

Cluster deletion and clique partitioning in graphs with bounded clique number
von: Galesi, Nicola, et al.
Veröffentlicht: (2025)

On 3-Coloring of $(2P_4,C_5)$-Free Graphs
von: Jelínek, Vít, et al.
Veröffentlicht: (2020)

Efficient Decomposition of Forman-Ricci Curvature on Vietoris-Rips Complexes and Data Applications
von: de Souza, Danillo Barros, et al.
Veröffentlicht: (2025)

Solving the Graph Burning Problem for Large Graphs
von: Pereira, Felipe de Carvalho, et al.
Veröffentlicht: (2024)

Reconfiguring homomorphisms to reflexive graphs via a simple reduction
von: Mühlenthaler, Moritz, et al.
Veröffentlicht: (2024)

Zero-free regions of partition functions with applications to algorithms and graph limits
von: Regts, Guus
Veröffentlicht: (2015)

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
von: Galby, Esther, et al.
Veröffentlicht: (2024)

Optimal Hardness of Online Algorithms for Large Independent Sets
von: Gamarnik, David, et al.
Veröffentlicht: (2025)

On the joint embedding property for cographs and trees
von: Carter, Daniel
Veröffentlicht: (2024)

On the Complexity of Distance-$d$ Independent Set Reconfiguration
von: Hoang, Duc A.
Veröffentlicht: (2022)

Integral Biflow Maximization
von: Ding, Guoli, et al.
Veröffentlicht: (2024)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
von: Patzner, Julian, et al.
Veröffentlicht: (2024)

Bicriteria Submodular Maximization
von: Feldman, Moran, et al.
Veröffentlicht: (2025)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
von: Bonnet, Édouard, et al.
Veröffentlicht: (2024)

Online Trading as a Secretary Problem Variant
von: Chen, Xujin, et al.
Veröffentlicht: (2026)

Pathographs and some (un)decidability results
von: Carter, Daniel, et al.
Veröffentlicht: (2025)

The Generalized Double Pouring Problem: Analysis, Bounds and Algorithms
von: Jäger, Gerold, et al.
Veröffentlicht: (2025)

Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints
von: Schwardt, J., et al.
Veröffentlicht: (2025)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
von: Heimann, Sophia, et al.
Veröffentlicht: (2025)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
von: Michel, Stefan
Veröffentlicht: (2025)

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
von: Baste, Julien, et al.
Veröffentlicht: (2019)

The Complexity of Distance-$r$ Dominating Set Reconfiguration
von: Banerjee, Niranka, et al.
Veröffentlicht: (2023)