Random knapsack in expected polynomial time
From MaRDI portal
Publication:5917572
DOI10.1016/j.jcss.2004.04.004zbMath1062.90037OpenAlexW3029201735MaRDI QIDQ5917572
Publication date: 18 November 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2004.04.004
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Boolean programming (90C09)
Related Items
Decision-making based on approximate and smoothed Pareto curves, Integer optimization with penalized fractional values: the knapsack case, Smoothed Analysis of Local Search Algorithms, Smoothed Analysis of the Successive Shortest Path Algorithm, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm, Smoothed analysis of integer programming, Multi-objective Problems in Terms of Relational Algebra, The smoothed number of Pareto-optimal solutions in bicriteria integer optimization, Smoothed performance guarantees for local search, Bounds for the Convergence Time of Local Search in Scheduling Problems, On smoothed analysis of quicksort and Hoare's find, Smoothed analysis of partitioning algorithms for Euclidean functionals, The Smoothed Number of Pareto-Optimal Solutions in Non-integer Bicriteria Optimization, A universally-truthful approximation scheme for multi-unit auctions, Performance guarantees for scheduling algorithms under perturbed machine speeds, Lower Bounds for the Smoothed Number of Pareto Optimal Solutions, Shortest paths with a cost constraint: a probabilistic analysis, On Geometric Set Cover for Orthants, Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An algorithm for the solution of the 0-1 knapsack problem
- Probabilistic analysis of the subset-sum problem
- Average saving effects in enumerative methods for solving knapsack problems
- A minimal algorithm for the multiple-choice knapsack problem
- New trends in exact algorithms for the \(0-1\) knapsack problem
- Efficient cryptographic schemes provably as secure as subset sum
- Discrete Dynamic Programming and Capital Allocation
- On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
- Probabilistic Analysis of the Multidimensional Knapsack Problem
- An Algorithm for Large Zero-One Knapsack Problems
- Computing Partitions with Applications to the Knapsack Problem
- Average-Case Analysis of Off-Line and On-Line Knapsack Problems
- Exponentially small bounds on the expected optimum of the partition and subset sum problems
- Smoothed analysis of algorithms
- Discrete-Variable Extremum Problems
- Random knapsack in expected polynomial time
