Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Polynomial time approximation schemes and parameterized complexity
- Approximation algorithms for a bi-level knapsack problem
- Primal-dual algorithms for precedence constrained covering problems
- The approximability of the weighted Hamiltonian path completion problem on a tree
- Approximation algorithms for the capacitated plant allocation problem
- Complexity of some parametric integer and network programming problems
- Engineering branch-and-cut algorithms for the equicut problem
- Job-shop scheduling in a body shop
- Approximation of the supply scheduling problem
- Greedy algorithms for the single-demand facility location problem
- Packing under convex quadratic constraints
- PTAS for densest \(k\)-subgraph in interval graphs
- Capacitated domination problem
- Orienting graphs to optimize reachability
- On the approximability of the two-phase knapsack problem
- Approximation scheduling algorithms: a survey
- A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
- On different approximation criteria for subset product problems
- A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width
- Scheduling split intervals with non-uniform demands
- On inequalities with bounded coefficients and pitch for the min knapsack polytope
- Reductions between scheduling problems with non-renewable resources and knapsack problems
- Packing under convex quadratic constraints
- Priority algorithms for the subset-sum problem
- Algorithms for the bounded set-up knapsack problem
- Optimizing a mail-order with discount and shipping costs
- Efficient approximation algorithms for the subset-sums equality problem.
- PARTITIONING TREES OF SUPPLY AND DEMAND
- Approximation algorithms for orthogonal packing problems for hypercubes
- Approximation algorithms and relaxations for a service provision problem on a telecommunication network
- Complexity and approximability results for slicing floorplan designs.
- Distributed approximation of k-service assignment
- Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
- On regularity of Max-CSPs and Min-CSPs
- Minimizing total weighted late work in a proportionate flow shop with job rejection
- Average sensitivity of the knapsack problem
- The unbounded knapsack problem
- Coordinating scheduling and rejection decisions in a two-machine flow shop scheduling problem
- Equivalence of some different maintenance activities in single-machine scheduling
- On fixed-parameter tractability and approximability of NP optimization problems
- The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem
- Exponential-time approximation of weighted set cover
- A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint
- A fast asymptotic approximation scheme for bin packing with rejection
- A theory of auto-scaling for resource reservation in cloud services
- A universally-truthful approximation scheme for multi-unit auctions
- Simple FPTAS for the subset-sums ratio problem
- Approximation schemes for generalized two-dimensional vector packing with application to data placement
- Minimum and worst-case performance ratios of rollout algorithms
- A survey on combinatorial optimization in dynamic environments
- A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
- Non deterministic polynomial optimization problems and their approximations
- Approximate and exact algorithms for the fixed-charge knapsack problem
- An FPTAS for the -modular multidimensional knapsack problem
- General bounds for incremental maximization
- Multistage knapsack
- Exact algorithms and approximation schemes for proportionate flow shop scheduling with step-deteriorating processing times
- Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties
- Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
- Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble
- Approximability of partitioning graphs with supply and demand
- FPTAS for half-products minimization with scheduling applications
- Playing monotone games to understand learning behaviors
- Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
- On a class of covering problems with variable capacities in wireless networks
- The online knapsack problem with incremental capacity
- Extended formulations in combinatorial optimization
- Primal-dual algorithms for precedence constrained covering problems
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
- Single machine scheduling with semi-resumable machine availability constraints
- 2D knapsack: packing squares
- Single-vendor multi-buyer inventory coordination under private information
- Vector bin packing with multiple-choice
- An approximation scheme for the two-stage, two-dimensional knapsack problem
- Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
- Resource allocation problem under single resource assignment
- Scheduling with variable-length calibrations: two agreeable variants
- Robust Optimization with Continuous Decision-Dependent Uncertainty with applications to demand response management
- Fast approximation algorithm for job sequencing with deadlines
- An efficient pruning algorithm for value independent knapsack problem using a DAG structure
- Approximation schemes for knapsack problems with shelf divisions
- Bin packing can be solved within 1+epsilon in linear time
- Online unbounded knapsack
- A PTAS for weight constrained Steiner trees in series--parallel graphs.
- Hybrid rounding techniques for knapsack problems
- Approximation schemes for subset-sums ratio problems
- Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times
- The knapsack problem with generalized upper bounds
- A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
- Shrinking maxima, decreasing costs: new online packing and covering problems
- On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Approximation algorithms for scheduling with reservations
- Toward a model for backtracking and dynamic programming
- Heuristic methods and applications: A categorized survey
- An asymptotically exact polynomial algorithm for equipartition problems
- Optimal delivery time quotation in supply chains to minimize tardiness and delivery costs
- On maximal and minimal triangular planar graphs: an optimization approach
- On the complexity and approximation of the maximum expected value all-or-nothing subset
This page was built for publication: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4114965)
