Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

DOI10.1145/321906.321909zbMath0345.90049OpenAlexW2026891055WikidataQ89143297 ScholiaQ89143297MaRDI QIDQ4114965

Oscar H. Ibarra, Chul Eung Kim

Publication date: 1975

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321906.321909

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

Packing Under Convex Quadratic Constraints, A Theory of Auto-Scaling for Resource Reservation in Cloud Services, Complexity of some parametric integer and network programming problems, Algorithms with guarantee value for knapsack problems, Primal-Dual Algorithms for Precedence Constrained Covering Problems, DIAMETER-CONSTRAINED STEINER TREES, Solving 0 - 1 knapsack problem by artificial chemical reaction optimization algorithm with a greedy strategy, A survey on combinatorial optimization in dynamic environments, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, On maximal and minimal triangular planar graphs: an optimization approach, Resource allocation problem under single resource assignment, SINGLE-MACHINE SCHEDULING WITH PROPORTIONALLY DETERIORATING JOBS SUBJECT TO AVAILABILITY CONSTRAINTS, Coupled-Tasks in Presence of Bipartite Compatibilities Graphs, Optimal Allocation for Chunked-Reward Advertising, Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines, Unnamed Item, On the approximability of the maximum common subgraph problem, Robust Optimization with Continuous Decision-Dependent Uncertainty with applications to demand response management, Integer knapsack problems with profit functions of the same value range, Learning-augmented algorithms for online subset sum, Some complexity and approximation results for coupled-tasks scheduling problem according to topology, Two-agent single-machine scheduling with release dates to minimize the makespan, Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties, Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach, Improved Algorithm for Resource Allocation Problems, On Bilevel Optimization with Inexact Follower, The Unbounded Knapsack Problem, Adaptive Submodular Ranking and Routing, Capacitated Domination Problem, Polynomially bounded minimization problems which are hard to approximate, ONLINE AND SEMI-ONLINE SCHEDULING ON CAPACITATED TWO-PARALLEL MACHINES, 2D Knapsack: Packing Squares, Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Clique Clustering Yields a PTAS for max-Coloring Interval Graphs, Rational solutions of the graphsack problem, Extended formulations in combinatorial optimization, Extended formulations in combinatorial optimization, Worst-case analysis of greedy algorithms for the subset-sum problem, Unnamed Item, The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem, Unnamed Item, The Prize-collecting Call Control Problem on Weighted Lines and Rings, Approximation algorithms for scheduling with reservations, Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation, Convex Relaxations and Integrality Gaps, PARTITIONING TREES OF SUPPLY AND DEMAND, A Dynamic Programming Approach for a Class of Robust Optimization Problems, NP-Complete operations research problems and approximation algorithms, A Survey on Approximation Algorithms for Scheduling with Machine Unavailability, Approximation scheduling algorithms: a survey, Two Dimensional Knapsack with Unloading Constraints, A logarithmic approximation for unsplittable flow on line graphs, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier, Unnamed Item, A faster FPTAS for knapsack problem with cardinality constraint, Approximation schemes for knapsack problems with shelf divisions, An asymptotically exact polynomial algorithm for equipartition problems, On different approximation criteria for subset product problems, An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, Approximation algorithms for the capacitated plant allocation problem, The online knapsack problem with incremental capacity, Parallel approximation schemes for subset sum and knapsack problems, The principle of optimality in the design of efficient algorithms, Shrinking maxima, decreasing costs: new online packing and covering problems, Orienting graphs to optimize reachability, Hard constraint satisfaction problems have hard gaps at location 1, The economic lot-sizing problem with an emission capacity constraint, Joint performance of greedy heuristics for the integer knapsack problem, Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval, A new enumeration scheme for the knapsack problem, Polynomial time approximation schemes for class-constrained packing problems, On an approximation measure founded on the links between optimization and polynomial approximation theory, Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval, On fixed-parameter tractability and approximability of NP optimization problems, Polynomial time approximation schemes and parameterized complexity, The knapsack problem with generalized upper bounds, Geometric relationship between parallel hyperplanes, quadrics, and vertices of a hypercube, Partially ordered knapsack and applications to scheduling, Reoptimizing the 0-1 knapsack problem, Ratio combinatorial programs, Reoptimization of maximum weight induced hereditary subgraph problems, 2D knapsack: packing squares, Approximation algorithms for a bi-level knapsack problem, Approximation algorithms and relaxations for a service provision problem on a telecommunication network, Strong LP formulations for scheduling splittable jobs on unrelated machines, Online removable knapsack with limited cuts, Complexity and approximability results for slicing floorplan designs., An efficient fully polynomial approximation scheme for the Subset-Sum problem., Online minimization knapsack problem, A PTAS for weight constrained Steiner trees in series--parallel graphs., Approximation schemes for generalized two-dimensional vector packing with application to data placement, Minimum and worst-case performance ratios of rollout algorithms, Knapsack problem with probability constraints, Exact algorithms for the guillotine strip cutting/packing problem., Vector bin packing with multiple-choice, Non deterministic polynomial optimization problems and their approximations, Discrete extremal problems, An approximation scheme for the two-stage, two-dimensional knapsack problem, Toward a model for backtracking and dynamic programming, Fast approximation algorithm for job sequencing with deadlines, A job-shop problem with one additional resource type, General approximation algorithms for some arithmetical combinatorial problems, A fully polynomial approximation algorithm for the 0-1 knapsack problem, Bin packing can be solved within 1+epsilon in linear time, A heuristic method for the design of minimum weight trusses using discrete member sizes, On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems., A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem., The multidimensional 0-1 knapsack problem: an overview., Single machine scheduling with semi-resumable machine availability constraints, Improved approximation algorithms for the average-case tree searching problem, On the two-dimensional knapsack problem, Single-vendor multi-buyer inventory coordination under private information, Reductions between scheduling problems with non-renewable resources and knapsack problems, Optimal and efficient adaptation in distributed real-time systems with discrete rates, Embedding decision-analytic control in a learning architecture, Approximation algorithms on 0--1 linear knapsack problem with a single continuous variable, Scheduling vessels and container-yard operations with conflicting objectives, Bandwidth allocation in cellular networks with multiple interferences, Approximate formulations for 0-1 knapsack sets, An improved approximation scheme for variable-sized bin packing, Nonconvex piecewise linear knapsack problems, A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem, A total-value greedy heuristic for the integer knapsack problem, Capacitated domination problem, Partitioning graphs of supply and demand, Playing monotone games to understand learning behaviors, 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, Exponential-time approximation of weighted set cover, A note on graph balancing problems with restrictions, Clique clustering yields a PTAS for max-coloring interval graphs, Approximate algorithms for some generalized knapsack problems, Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval, Approximability of partitioning graphs with supply and demand, FPTAS for half-products minimization with scheduling applications, Approximated consistency for the automatic recording constraint, Approximate solution of the control problem of supplies with many intervals and concave cost functions, The zone hopping problem, Approximation algorithms for single machine scheduling with one unavailability period, Approximate algorithms for the Knapsack problem on parallel computers, A successive approximation algorithm for the multiple knapsack problem, Priority algorithms for the subset-sum problem, Parallel machine batching and scheduling with deadlines, Weighted sum coloring in batch scheduling of conflicting jobs, Approximation algorithms for knapsack problems with cardinality constraints, Approximation algorithms for orthogonal packing problems for hypercubes, Scheduling three chains on two parallel machines, Recent trends in combinatorial optimization, Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Fast fully polynomial approximation schemes for minimizing completion time variance, Approximation schemes for the subset-sum problem: Survey and experimental analysis, Completeness in approximation classes, PTAS for densest \(k\)-subgraph in interval graphs, The multidimensional 0-1 knapsack problem -- bounds and computational aspects, Multistage knapsack, On regularity of Max-CSPs and Min-CSPs, An FPTAS for the parametric knapsack problem, Approximating multidimensional subset sum and Minkowski decomposition of polygons, An efficient pruning algorithm for value independent knapsack problem using a DAG structure, Proportionate flow shop scheduling with multi-agents to maximize total gains of JIT jobs, Approximation schemes for a class of subset selection problems, On the complexity of working set selection, The platform design problem, A nonlinear knapsack problem, The stochastic bilevel continuous knapsack problem with uncertain follower's objective, Selecting a subset of diverse points based on the squared Euclidean distance, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Approximation schemes for subset-sums ratio problems, Approximation and online algorithms for multidimensional bin packing: a survey, The sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees, Lower bounds on the performance of online algorithms for relaxed packing problems, An additive approximation scheme for the Nash social welfare maximization with identical additive valuations, On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks, Primal-dual algorithms for precedence constrained covering problems, A new fully polynomial time approximation scheme for the interval subset sum problem, A faster FPTAS for the unbounded knapsack problem, Computing knapsack solutions with cardinality robustness, Ranking robustness and its application to evacuation planning, A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint, On inequalities with bounded coefficients and pitch for the min knapsack polytope, Group parking permit problems, Approximating connected safe sets in weighted trees, Knapsack with variable weights satisfying linear constraints, The knapsack problem with neighbour constraints, Knapsack problems: a parameterized point of view, Scheduling two-stage jobs on multiple flowshops, Minimum cost partitions of trees with supply and demand, Equivalence of some different maintenance activities in single-machine scheduling, On the complexity and approximation of the maximum expected value all-or-nothing subset, Finding well-balanced pairs of edge-disjoint trees in edge-weighted graphs, Scheduling of pipelined operator graphs, Job-shop scheduling in a body shop, Bounded parallel-batching scheduling with two competing agents, Minimum diameter cost-constrained Steiner trees, The online knapsack problem: advice and randomization, Scheduling jobs with a V-shaped time-dependent processing time, Simple FPTAS for the subset-sums ratio problem, Bin covering with cardinality constraints, Scheduling split intervals with non-uniform demands, Approximation for knapsack problems with multiple constraints, Greedy algorithms for the single-demand facility location problem, Online removable knapsack problem under convex function, Cut problems in graphs with a budget constraint, Distributed approximation of \(k\)-service assignment, A universally-truthful approximation scheme for multi-unit auctions, Scheduling with variable-length calibrations: two agreeable variants, Robust single machine scheduling with a flexible maintenance activity, Online budgeted maximum coverage, Algorithms for the bounded set-up knapsack problem, Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times, Scheduling a two-stage flowshop under makespan constraint, A fast asymptotic approximation scheme for bin packing with rejection, Order acceptance and scheduling with machine availability constraints, A single-item economic lot-sizing problem with a non-uniform resource: Approximation, Minimization of ordered, symmetric half-products, Hybrid rounding techniques for knapsack problems, Optimal delivery time quotation in supply chains to minimize tardiness and delivery costs, Approximation of the supply scheduling problem, Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem, On the complexity of the single machine scheduling problem minimizing total weighted delay penalty, On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space, On the approximability of the two-phase knapsack problem, Scheduling many types of calibrations, Lift-and-project methods for set cover and knapsack, An FPTAS for the knapsack problem with parametric weights, Stochastic on-line knapsack problems, Average-case analysis of a greedy algorithm for the 0/1 knapsack problem., Malleable scheduling for flows of jobs and applications to MapReduce, Dividing splittable goods evenly and with limited fragmentation, New results for scheduling to minimize tardiness on one machine with rejection and related problems, Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width, Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates, A new linear storage, polynomial-time approximation scheme for the subset-sum problem, Least-cost partition algorithms, Heuristic methods and applications: A categorized survey, Techniques and results on approximation algorithms for packing circles, The approximability of the weighted Hamiltonian path completion problem on a tree, Strongly polynomial FPTASes for monotone dynamic programs, Approximate and exact algorithms for the fixed-charge knapsack problem, 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, On weighted vs unweighted versions of combinatorial optimization problems, Efficiently computing succinct trade-off curves, A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems, Optimizing a mail-order with discount and shipping costs, The quadratic 0-1 knapsack problem with series-parallel support, Efficient approximation algorithms for the subset-sums equality problem., Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem., Improved approximation algorithms for a bilevel knapsack problem, Offline black and white bin packing, Approximation schemes for multiperiod binary knapsack problems, An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem, General bounds for incremental maximization, Packing under convex quadratic constraints