Parameterized Approximation Scheme for the Multiple Knapsack Problem

No abstract is available for this paper.

• Publication year

  2009

• Venue

  SIAM journal on computing (Print)

• Publication date

  2009-01-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/080731207
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Parameterized Complexity and Approximation Algorithms

  2008cited by this paper
• Approximation Algorithms for Scheduling with Reservations

  2007cited by this paper
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

  2005influential reference
• Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

  2004cited by this paper
• Blow-Ups, Win/Win's, and Crown Rules: Some New Directions in FPT

  2003cited by this paper
• A PTAS for the multiple knapsack problem

  2000cited by this paper
• Approximate Max-Min Resource Sharing for Structured Concave Optimization

  2000cited by this paper
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

  1999cited by this paper
• A New Fully Polynomial Time Approximation Scheme for the Knapsack Problem

  1999cited by this paper
• Approximability of scheduling with fixed jobs

  1999cited by this paper
• Approximate strip packing

  1996influential reference
• Selecting the median

  1995cited by this paper
• An approximation algorithm for the generalized assignment problem

  1993cited by this paper
• Fast approximation algorithms for fractional packing and covering problems

  1991cited by this paper
• Knapsack Problems: Algorithms and Computer Implementations

  1990cited by this paper
• Approximation algorithms for scheduling unrelated parallel machines

  1987cited by this paper
• An Algorithm for Large Zero-One Knapsack Problems

  1980cited by this paper
• Fast approximation algorithms for knapsack problems

  1977cited by this paper
• Time Bounds for Selection

  1973cited by this paper

• Job Scheduling under Base and Additional Fees, with Applications to Mixed-Criticality Scheduling

  2025cites this paper
• Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically

  2024cites this paper
• Approximating Knapsack and Partition via Dense Subset Sums

  2023cites this paper
• An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding

  2023cites this paper
• An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding

  2023cites this paper
• Improved Approximation for Two-dimensional Vector Multiple Knapsack

  2023influential citation
• Equitable Network-Aware Decarbonization of Residential Heating at City Scale

  2023cites this paper
• A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint

  2022cites this paper
• An FPTAS for Quickest Multi-commodity Contraflow Problem with Asymmetric Transit Times

  2022cites this paper
• Technical Note - An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem

  2022cites this paper
• Pricing Problems with Buyer Preselection

  2022cites this paper
• Knapsack problems - An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems

  2022cites this paper
• An EPTAS for Budgeted Matroid Independent Set

  2022cites this paper
• Approximation Algorithms for Interdiction Problem with Packing Constraints

  2022cites this paper
• A PTAS for Packing Hypercubes into a Knapsack

  2022cites this paper
• Scheduling multiple two-stage flowshops with a deadline

  2022cites this paper
• A PTAS for parallel two-stage flowshops under makespan constraint

  2022cites this paper
• CS 583: Approximation Algorithms

  2021cites this paper
• Scheduling shuttle ambulance vehicles for COVID-19 quarantine cases, a multi-objective multiple 0–1 knapsack model with a novel Discrete Binary Gaining-Sharing knowledge-based optimization algorithm

  2021cites this paper
• A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection Problems

  2021cites this paper
• Robust Online Algorithms for Dynamic Choosing Problems

  2021influential citation
• A survey on runtime testing of dynamically adaptable and distributed systems

  2021cites this paper
• Intelligent system for recruitment decision making using an alternative parallel-sequential genetic algorithm

  2021cites this paper
• Synthetic Data Generation with Differential Privacy via Bayesian Networks

  2021cites this paper
• Scheduling on Multiple Two-Stage Flowshops with a Deadline

  2021cites this paper
• Approximation Schemes for Multiperiod Binary Knapsack Problems

  2021cites this paper
• A Tight Deterministic Algorithm for the Submodular Multiple Knapsack Problem

  2021cites this paper
• An almost optimal approximation algorithm for monotone submodular multiple knapsack

  2021cites this paper
• Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping

  2020cites this paper
• Deterministic Algorithms for the Submodular Multiple Knapsack Problem

  2020cites this paper
• Algorithmic approaches to the multiple knapsack assignment problem

  2020cites this paper
• Elements of Scheduling

  2020cites this paper
• Simple Deterministic Approximation for Submodular Multiple Knapsack Problem

  2020cites this paper
• A new upper bound for the multiple knapsack problem

  2020cites this paper
• Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time

  2020influential citation
• Exploring search space trees using an adapted version of Monte Carlo tree search for a combinatorial optimization problem

  2020cites this paper
• Market Driven Multi-Resource Allocation

  2020cites this paper
• Tight Algorithms for the Submodular Multiple Knapsack Problem

  2020cites this paper
• A $(1-e^{-1}-\varepsilon)$-Approximation for the Monotone Submodular Multiple Knapsack Problem

  2020cites this paper
• A (1 − e − 1 − ε ) -Approximation for the Monotone Submodular Multiple Knapsack Problem

  2020cites this paper
• On inequalities with bounded coefficients and pitch for the min knapsack polytope

  2020cites this paper
• Assortment Planning From A Large Universe

  2020cites this paper
• Tight Approximations for Modular and Submodular Optimization with D-resource Multiple Knapsack Constraints

  2020cites this paper
• A Fine-Grained Perspective on Approximating Subset Sum and Partition

  2020cites this paper
• Combinatorial Multi-Armed Bandit Based Unknown Worker Recruitment in Heterogeneous Crowdsensing

  2020cites this paper
• A Greedy Algorithm for Jobs Allocation in a Multiprocessor System

  2019cites this paper
• D S ] 6 M ay 2 01 9 A Subquadratic Approximation Scheme for Partition

  2019cites this paper
• A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection Problems: A GPQIEA for Subset Selection

  2019cites this paper
• On the approximability of the two-phase knapsack problem

  2019cites this paper
• Faster Pseudopolynomial Time Algorithms for Subset Sum

  2019influential citation
• A Faster FPTAS for Knapsack Problem With Cardinality Constraint

  2019cites this paper
• Estimating the probability of meeting a deadline in schedules and plans

  2019cites this paper
• Efficient Multi-Resource, Multi-Unit VCG Auction

  2019cites this paper
• DP-BASED ALGORITHM AND FPTAS FOR THE KNAPSACK SHARING AND RELATED PROBLEMS

  2019cites this paper
• Edge-Assisted Stream Scheduling Scheme for the Green-Communication-Based IoT

  2019cites this paper
• On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

  2019influential citation
• Knapsack Problem With Cardinality Constraint: A Faster FPTAS Through the Lens of Numerical Analysis and Applications

  2019cites this paper
• A Resource-Aware Model-Based Framework for Load Testing of WS-BPEL Compositions

  2018cites this paper
• Approximation Schemes for 0-1 Knapsack

  2018cites this paper
• Profit Maximization of NFV-Enabled Request Admissions in SDNs

  2018cites this paper
• D S ] 6 A pr 2 01 8 Subquadratic Approximation Scheme for Partition

  2018influential citation
• Improved Algorithm for Resource Allocation Problems

  2018cites this paper
• QoE enhancement schemes for video in converged OFDMA wireless networks and EPONS

  2018cites this paper
• On bounded pitch inequalities for the min-knapsack polytope

  2018influential citation
• A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

  2018cites this paper
• On Fair Price Discrimination in Multi-Unit Markets

  2018cites this paper
• Packing Groups of Items into Multiple Knapsacks

  2018cites this paper
• On Social Envy-Freeness in Multi-Unit Markets

  2018cites this paper
• Hub Network Design and Discrete Location: Economies of Scale, Reliability and Service Level Considerations

  2018cites this paper
• Two-stage Pandora ’ s Box for Product Ranking

  2018cites this paper
• Approximation Algorithms for a Two-Phase Knapsack Problem

  2018cites this paper
• Introduction, Overview, and Notation

  2018cites this paper
• On Approximating (Sparse) Covering Integer Programs

  2018influential citation
• Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints

  2018cites this paper
• On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks

  2017cites this paper
• A new fully polynomial time approximation scheme for the interval subset sum problem

  2017influential citation
• Truthfulness with value-maximizing bidders: On the limits of approximation in combinatorial markets

  2017cites this paper
• Approximation and online algorithms for multidimensional bin packing: A survey

  2017cites this paper
• General bounds for incremental maximization

  2017cites this paper
• An FPTAS for the Knapsack Problem with Parametric Weights

  2017cites this paper
• Scheduling Monotone Moldable Jobs in Linear Time

  2017influential citation
• Knapsack Problems with Side Constraints

  2017cites this paper
• Flexible Resource Allocation for Network Problems

  2017cites this paper
• A new fully polynomial time approximation scheme for the interval subset sum problem

  2017influential citation
• An exact algorithm for the modular hub location problem with single assignments

  2017cites this paper
• Name Your Own Price on Data Marketplaces

  2017cites this paper
• An FPTAS for the parametric knapsack problem

  2017cites this paper
• Truthfulness with Value-Maximizing Bidders

  2016cites this paper
• Energy Synchronized Task Assignment in Rechargeable Sensor Networks

  2016cites this paper
• G T ] 2 9 Ju l 2 01 6 Envy-Free Pricing in Multi-unit Markets ∗

  2016cites this paper
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum

  2016cites this paper
• G T ] 28 F eb 2 01 6 Envy-Free Pricing in Multi-unit Markets ∗

  2016cites this paper
• Approximate composable truthful mechanism design

  2016cites this paper
• Column Generation at Strip Level for the k-Staged Two-Dimensional Cutting Stock Problem

  2016cites this paper
• Fair Knapsack Pricing for Data Marketplaces

  2016cites this paper
• Proportionate flow-shop scheduling with rejection

  2016cites this paper
• Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

  2016cites this paper
• Sequential testing of a series system in batches

  2015cites this paper
• The multiple knapsack problem with compatible bipartite graphs

  2015cites this paper
• On the existence of compact ε-approximated formulations for knapsack in the original space

  2015cites this paper