Copertina

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Tran, Tan D., Pham, Canh V.
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms Artificial Intelligence Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
di: Pham, Canh V.
Pubblicazione: (2024)

Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem
di: Nguyen, Hue T., et al.
Pubblicazione: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
di: Chen, Shengminjie, et al.
Pubblicazione: (2026)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
di: Srivastava, Ajitesh, et al.
Pubblicazione: (2026)

Maximization of Approximately Submodular Functions
di: Horel, Thibaut, et al.
Pubblicazione: (2024)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
di: Thejaswi, Suhas, et al.
Pubblicazione: (2024)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
di: Banik, Aritra, et al.
Pubblicazione: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
di: Gadekar, Ameet, et al.
Pubblicazione: (2025)

Avoiding Obfuscation with Prover-Estimator Debate
di: Brown-Cohen, Jonah, et al.
Pubblicazione: (2025)

Sorting by Strip Swaps is NP-Hard
di: Roy, Swapnoneel, et al.
Pubblicazione: (2025)

$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression
di: Nye, Logan
Pubblicazione: (2025)

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

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
di: Zhu, Yanhui, et al.
Pubblicazione: (2024)

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
di: Blum, Avrim, et al.
Pubblicazione: (2025)

Continuous Non-monotone DR-submodular Maximization with Down-closed Convex Constraint
di: Chen, Shengminjie, et al.
Pubblicazione: (2023)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

The Complexity of Maximal Common Subsequence Enumeration
di: Buzzega, Giovanni, et al.
Pubblicazione: (2025)

TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm
di: Amini, Amin
Pubblicazione: (2024)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
di: Mao, Songtao
Pubblicazione: (2026)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
di: Dhar, Anubhav, et al.
Pubblicazione: (2025)

Approximate Algorithms for Chamfer Distance Under Translation
di: Halevi, Gil, et al.
Pubblicazione: (2026)

Size Minimization For Multi-Output AND-Functions
di: Armbruster, Susanne
Pubblicazione: (2024)

Algorithms and Hardness for Estimating Statistical Similarity
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2025)

Improved Hardness-of-Approximation for Token Swapping
di: Hiken, Sam, et al.
Pubblicazione: (2024)

Knapsack on Graphs with Relaxed Neighborhood Constraints
di: Dey, Palash, et al.
Pubblicazione: (2025)

Exact and Approximate Algorithms for Polytree Learning
di: Harviainen, Juha, et al.
Pubblicazione: (2026)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
di: Bilò, Davide, et al.
Pubblicazione: (2025)

Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
di: Chen, Yixin, et al.
Pubblicazione: (2020)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
di: DeHaan, Ian, et al.
Pubblicazione: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
di: Chou, Chi-Ning, et al.
Pubblicazione: (2021)

A Note on Approximability of Densest At-Least-k-Subgraph
di: Laekhanukit, Bundit, et al.
Pubblicazione: (2026)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
di: Bhaskar, Umang, et al.
Pubblicazione: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
di: Singer, Noah G., et al.
Pubblicazione: (2026)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
di: Grossman, Ofer, et al.
Pubblicazione: (2023)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
di: Bai, Tian, et al.
Pubblicazione: (2026)