2017/10/24 by Frank Gurski, Gurski, Frank, Carolin Rehs +1 · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Continuous knapsack problem #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Knapsack problem #Mathematical optimization #Mathematics #Optimization and Packing Problems #Polynomial-time approximation scheme #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1710.08953
published in arXiv (Cornell University) (Cornell University) · 26 pages; 9 Figures; 4 Tables
arxiv created 2017/10/24 · openalex publication_date 2017/10/24 · arxiv updated 2017/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce methods to count and enumerate all maximal independent, all maximum independent sets, and all independent sets in threshold graphs and k-threshold graphs. Within threshold graphs and k-threshold graphs independent sets correspond to feasible solutions in related knapsack instances. We give several characterizations for knapsack instances and multidimensional knapsack instances which allow an equivalent graph. This allows us to solve special knapsack instances as well as special multidimensional knapsack instances for fixed number of dimensions in polynomial time. We also conclude lower bounds on the number of necessary bins within several bin packing problems.