Imagen de Portada

A simple $(2+ε)$-approximation for knapsack interdiction

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Weninger, Noah
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

An O(nlogn) approximate knapsack algorithm
por: Dawes, Nick
Publicado: (2025)

Interdiction of minimum spanning trees and other matroid bases
por: Weninger, Noah, et al.
Publicado: (2024)

Dependent randomized rounding for clustering and partition systems with knapsack constraints
por: Harris, David G., et al.
Publicado: (2017)

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
por: Bshouty, Nader H., et al.
Publicado: (2026)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
por: Yang, Yang
Publicado: (2024)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
por: Yang, Yang
Publicado: (2025)

A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
por: Fox, Emily
Publicado: (2023)

On contention resolution for the hypergraph matching, knapsack, and $k$-column sparse packing problems
por: Sergeev, Ivan
Publicado: (2024)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
por: Bathie, Gabriel, et al.
Publicado: (2025)

Sketching approximations and LP approximations for finite CSPs are related
por: Singer, Noah G., et al.
Publicado: (2025)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
por: Mao, Xiao
Publicado: (2023)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
por: Singer, Noah G.
Publicado: (2025)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
por: Baligács, Júlia, et al.
Publicado: (2024)

A $O^*((2 + ε)^k)$ Time Algorithm for Cograph Deletion Using Unavoidable Subgraphs in Large Prime Graphs
por: Lafond, Manuel, et al.
Publicado: (2026)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
por: Adil, Deeksha, et al.
Publicado: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

Streaming approximation resistance of every ordering CSP
por: Singer, Noah G., et al.
Publicado: (2021)

ε-Cost Sharding: Scaling Hypergraph-Based Static Functions and Filters to Trillions of Keys
por: Vigna, Sebastiano
Publicado: (2025)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
por: Haeupler, Bernhard, et al.
Publicado: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
por: Solomon, Shay, et al.
Publicado: (2023)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
por: Haeupler, Bernhard, et al.
Publicado: (2024)

Beyond 2-approximation for k-Center in Graphs
por: Jin, Ce, et al.
Publicado: (2025)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
por: Armbruster, Alexander, et al.
Publicado: (2025)

Fast and simple unrooted dynamic forests
por: Berendsohn, Benjamin Aram
Publicado: (2023)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
por: Dhawan, Abhishek
Publicado: (2024)

A simple and efficient preprocessing step for convex hull problem
por: Heydari, Mohammad, et al.
Publicado: (2023)

Efficient parameterized approximation
por: Kratsch, Stefan, et al.
Publicado: (2025)

Dynamic framework for edge-connectivity maintenance of simple graphs
por: Wrobel, Blazej
Publicado: (2026)

New simple and fast quicksort algorithm for equal keys
por: Afereidoon, Parviz
Publicado: (2025)

A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma
por: Gupta, Sushmita, et al.
Publicado: (2025)

Fixed-sparsity matrix approximation from matrix-vector products
por: Amsel, Noah, et al.
Publicado: (2024)

New approximate distance oracles and their applications
por: Kadria, Avi, et al.
Publicado: (2025)

Bicriteria approximation for $k$-edge-connectivity
por: Nutov, Zeev, et al.
Publicado: (2025)

A framework for boosting matching approximation: parallel, distributed, and dynamic
por: Mitrović, Slobodan, et al.
Publicado: (2025)

A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs
por: Tsin, Yung H.
Publicado: (2023)

Non-Signaling Locality Lower Bounds for Dominating Set
por: Fleming, Noah, et al.
Publicado: (2026)

Improved bicriteria approximation for $k$-edge-connectivity
por: Nutov, Zeev
Publicado: (2025)

Improved girth approximation in weighted undirected graphs
por: Kadria, Avi, et al.
Publicado: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
por: Filtser, Arnold, et al.
Publicado: (2024)

On the cut-query complexity of approximating max-cut
por: Plevrakis, Orestis, et al.
Publicado: (2022)