Copertina

An Exact Solver for Submodular Knapsack Problems

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Münch, Sabine, Raach, Stephen
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms Discrete Mathematics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
di: Klimm, Max, et al.
Pubblicazione: (2022)

Approximating Submodular Matroid-Constrained Partitioning
di: Bérczi, Kristóf, et al.
Pubblicazione: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
di: Mizutani, Ryuhei
Pubblicazione: (2025)

Parameterized Complexity of Submodular Minimization under Uncertainty
di: Kakimura, Naonori, et al.
Pubblicazione: (2024)

A Unified Approach to Minimizing Symmetric Submodular Functions
di: Iwata, Satoru, et al.
Pubblicazione: (2026)

Cuts and Gauges for Submodular Width
di: Lanzinger, Matthias
Pubblicazione: (2026)

UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
di: Arhire, Andrei, et al.
Pubblicazione: (2025)

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

The Role of Dimension in the Online Chasing Problem
di: Papazov, Hristo
Pubblicazione: (2023)

Solving the Multiobjective Quasi-Clique Problem
di: Santos, Daniela Scherer dos, et al.
Pubblicazione: (2024)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
di: Wang, Chenhao
Pubblicazione: (2025)

Partially Ordered Sets Corresponding to the Partition Problem
di: Kubo, Susumu
Pubblicazione: (2024)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
di: Madathil, Jayakrishnan, et al.
Pubblicazione: (2024)

Algorithmic Results for Weak Roman Domination Problem in Graphs
di: Paul, Kaustav, et al.
Pubblicazione: (2024)

ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
di: Gallart, Joan Vendrell, et al.
Pubblicazione: (2025)

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
di: Chen, Yixin, et al.
Pubblicazione: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
di: Wang, Chen, et al.
Pubblicazione: (2024)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
di: Harada, Tsubasa, et al.
Pubblicazione: (2024)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
di: Disser, Yann, et al.
Pubblicazione: (2024)

Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem
di: Kaymakov, Kirill V., et al.
Pubblicazione: (2024)

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
di: Soulignac, Francisco J.
Pubblicazione: (2025)

Solving the List Coloring Problem through a Branch-and-Price algorithm
di: Lucci, Mauro, et al.
Pubblicazione: (2023)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
di: Manna, Bubai, et al.
Pubblicazione: (2024)

Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems
di: Duvignau, Romaric, et al.
Pubblicazione: (2024)

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
di: Tukan, Murad, et al.
Pubblicazione: (2024)

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

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
di: Holtgrefe, Niels, et al.
Pubblicazione: (2024)

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

Simultaneous Drawing of Layered Trees
di: Katheder, Julia, et al.
Pubblicazione: (2023)

Computing Approximate Pareto Frontiers for Submodular Utility and Cost Tradeoffs
di: Vombatkere, Karan, et al.
Pubblicazione: (2026)

The Strong Birthday Problem Revisited
di: Tripathy, Chijul B.
Pubblicazione: (2025)

Bipartite Exact Matching in P
di: Du, Yuefeng
Pubblicazione: (2026)

Problems on Group-labeled Matroid Bases
di: Hörsch, Florian, et al.
Pubblicazione: (2024)

On The Maximum Linear Arrangement Problem for Trees
di: Alemany-Puig, Lluís, et al.
Pubblicazione: (2023)

An Algebraic Approach to the Longest Path Problem
di: Khazali, Omar Al -
Pubblicazione: (2023)

Hardness of Burning Number Problem on Regular Graphs
di: Antony, Dhanyamol, et al.
Pubblicazione: (2026)

EPTAS for Hard Graph Cut Problems for Dense Graphs
di: Deguchi, Kaisei, et al.
Pubblicazione: (2026)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
di: Paschalidis, Phevos, et al.
Pubblicazione: (2023)

Exact Causal Attention with 10% Fewer Operations
di: Rybin, Dmitry, et al.
Pubblicazione: (2025)

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
di: Shook, James M., et al.
Pubblicazione: (2025)