Buchumschlag

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Klimm, Max, Knaack, Martin
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms Discrete Mathematics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An Exact Solver for Submodular Knapsack Problems
von: Münch, Sabine, et al.
Veröffentlicht: (2025)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
von: Disser, Yann, et al.
Veröffentlicht: (2024)

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
von: Tukan, Murad, et al.
Veröffentlicht: (2024)

Parameterized Complexity of Submodular Minimization under Uncertainty
von: Kakimura, Naonori, et al.
Veröffentlicht: (2024)

Generalized Assignment and Knapsack Problems in the Random-Order Model
von: Klimm, Max, et al.
Veröffentlicht: (2025)

A Unified Approach to Minimizing Symmetric Submodular Functions
von: Iwata, Satoru, et al.
Veröffentlicht: (2026)

Approximating Submodular Matroid-Constrained Partitioning
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
von: Mizutani, Ryuhei
Veröffentlicht: (2025)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
von: Wang, Chenhao
Veröffentlicht: (2025)

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
von: Chen, Yixin, et al.
Veröffentlicht: (2024)

ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
von: Gallart, Joan Vendrell, et al.
Veröffentlicht: (2025)

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
von: Schade, Jamico, et al.
Veröffentlicht: (2023)

Cuts and Gauges for Submodular Width
von: Lanzinger, Matthias
Veröffentlicht: (2026)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
von: Hao, Yimin, et al.
Veröffentlicht: (2025)

Functional design of efficient and parallelizable combinatorial generators using convolution
von: He, Xi, et al.
Veröffentlicht: (2025)

On the Parameterized Intractability of Determinant Maximization
von: Ohsaka, Naoto
Veröffentlicht: (2022)

A Unified Approach to Submodular Maximization Under Noise
von: Bhawalkar, Kshipra, et al.
Veröffentlicht: (2025)

Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
von: Brosse, Caroline, et al.
Veröffentlicht: (2024)

Stability in Graphs with Matroid Constraints
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Cutwidth Bounds via Vertex Partitions
von: Amarilli, Antoine, et al.
Veröffentlicht: (2025)

Temporal Graph Realization With Bounded Stretch
von: Mertzios, George B., et al.
Veröffentlicht: (2025)

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
von: Bandopadhyay, Susobhan, et al.
Veröffentlicht: (2023)

On the Structural Parameterizations of 2-Club with Triangle Constraints
von: Jacob, Ashwin, et al.
Veröffentlicht: (2025)

Nearly Tight Bounds on Testing of Metric Properties
von: Bao, Yiqiao, et al.
Veröffentlicht: (2024)

Optimal Padded Decomposition For Bounded Treewidth Graphs
von: Filtser, Arnold, et al.
Veröffentlicht: (2024)

Bounding $\varepsilon$-scatter dimension via metric sparsity
von: Bourneuf, Romain, et al.
Veröffentlicht: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2024)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
von: Abbasi, Ali, et al.
Veröffentlicht: (2026)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
von: Swamy, Chaitanya, et al.
Veröffentlicht: (2025)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
von: Harada, Tsubasa
Veröffentlicht: (2024)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
von: Arndt, Stephen, et al.
Veröffentlicht: (2026)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
von: Gaikwad, Ajinkya
Veröffentlicht: (2025)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
von: Bentert, Matthias, et al.
Veröffentlicht: (2026)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2022)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
von: German, Samuel
Veröffentlicht: (2026)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
von: Dutta, Kunal, et al.
Veröffentlicht: (2026)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
von: de Montgolfier, Fabien, et al.
Veröffentlicht: (2025)

Inverse matroid optimization under subset constraints
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Adversarial Configurations for the ReCom Transition Function
von: Gold, Micah
Veröffentlicht: (2026)

Cuts in Graphs with Matroid Constraints
von: Banik, Aritra, et al.
Veröffentlicht: (2024)