0-1 kNapsack problem FPTAS algorithm

  • Context: Graduate 
  • Thread starter Thread starter StIgM@
  • Start date Start date
  • Tags Tags
    Algorithm
Click For Summary
SUMMARY

The discussion centers on a variant of the 0-1 knapsack problem where the objective is to minimize costs while purchasing a specified quantity of a product from multiple farmers, each offering different quantities at varying prices. The mathematical formulation involves minimizing the cost function while ensuring the total quantity meets or exceeds the required amount. Participants confirm that this problem resembles the 0-1 knapsack problem and inquire about the applicability of Fully Polynomial-Time Approximation Schemes (FPTAS) algorithms for solving it. The complexity of the problem is acknowledged, with a note that precise problem formulation is essential for determining NP completeness.

PREREQUISITES
  • Understanding of 0-1 knapsack problem formulation
  • Familiarity with optimization algorithms, specifically FPTAS
  • Knowledge of linear programming and the simplex algorithm
  • Basic concepts of computational complexity and NP completeness
NEXT STEPS
  • Research FPTAS algorithms applicable to knapsack problems
  • Explore linear programming techniques, particularly the simplex method
  • Study the mathematical formulation of optimization problems
  • Investigate the complexity classes, focusing on NP and NP-complete problems
USEFUL FOR

Mathematicians, computer scientists, and optimization specialists interested in algorithm design and complexity theory, particularly those working on resource allocation problems.

StIgM@
Messages
8
Reaction score
0
I have the following 0-1 knapsack problem variant:

I want to buy X units of a product at min cost, and there are m farmers that offer:

- farmer 1: a11 units at cost c11, ..., a1n1 units at cost c1n1
...
- farmer m: am1 units at cost cm1, ..., amnm units at cost cmnm

and I can choose at most one option from each farmer.

Formally, I want to

Minimise \sum_{i=1}^{m} \sum_{j=1}^{n_i} x_{ij}c_{ij}

subject to \sum_{i=1}^{m} \sum_{j=1}^{n_i} x_{ij}a_{ij} >= X

where x_{ij}\in\{0,1\}

Could you please let me know if this problem resembles a variant of 0-1 knapsack problem?

Is there any FPTAS algorithm that suits this problem?

Thanks in advance

Note: It's not homework. The problem is different and this example is a simplification.
 
Last edited:
Mathematics news on Phys.org
If you only can decide between "buy all" and "do not buy" from a certain farmer, then it is a 0-1-problem. It is an ordinary optimization problem, so algorithms like the simplex algorithm should help. The complexity of the problem is another question, i.e. whether it is NP complete or not. Looks as it is at first sight, but to decide this the problem has to be stated very precisely and a proof is needed.
 

Similar threads

  • · Replies 12 ·
Replies
12
Views
3K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 15 ·
Replies
15
Views
2K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 3 ·
Replies
3
Views
5K
  • · Replies 0 ·
Replies
0
Views
1K