Skip to main content
5 votes
Accepted

Distributing resources for maximum gain

This is a knapsack problem. In the most basic version, you have a single resource (e.g., space in your knapsack) and you're trying to choose which items to put in it so you can carry the greatest ...
David Richerby's user avatar
2 votes

Best approach to resource allocation problem

Let us first show that your proposed greedy algorithm for the second restriction is not optimal. For this, consider a scenario with $e_1 = 1, e_2 = 3$ and $e_3 = 4$ as well as $d_1 = 1, d_2 = 2$ and $...
Watercrystal's user avatar
  • 1,526
2 votes

Why does garbage collection extend only to memory and not other resource types?

All memory is equal, if I ask for 1K, I don’t care where in the address space the 1K comes from. When I ask for a file handle, I want a handle to the file I wish to open. Having a file handle open ...
Ian Ringrose's user avatar
2 votes

NP-hardness of resource allocation problem

If you set $N = 2$, and $r_{i0} = r_{i1} = r_i$ for each $i$, and set $R = \frac12 \sum_{i \in [L]} r_i$, then the feasibility of this linear program is precisely the Partition problem. Namely, a ...
Mees de Vries's user avatar
1 vote
Accepted

Best approach to resource allocation problem

The second variant of your problem can be also stated as a Bin covering problem and vice-versa. Let us see how. You can assume $n$ bins of capacities: $(e_{1}+1)$, $\dotsc$, $(e_{n-1}+1)$ and $(e_{n}+...
Inuyasha Yagami's user avatar
1 vote

Minimum number of processes for the deadlock?

I would think that even with 5 processes, deadlock isn't possible. If 5 processes each need up to 2 of six identical resources, we could assume that each acquires one resources, and then we have 5 ...
gnasher729's user avatar
  • 30.6k
1 vote
Accepted

Problem class of assigning N persons to N tasks, zero costs with prefs

This problem is known as maximum matching of a bipartite graph. Basically let vertex $p_i$ (resp., $q_i$) represent the $i$th person (resp., task). And we connect $p_i$ and $q_j$ with an undirected ...
Lwins's user avatar
  • 370
1 vote

Reasoning about resources: "resource logics"?

Just learned about Bunched Logic which seems to fit the bill too.
Lance's user avatar
  • 2,243
1 vote

Reasoning about resources: "resource logics"?

Do you mean a resource-aware logic? If so, yes, there's linear logic [Girard, 1987] (as was already noted in the comments). It has had a big influence on the study of concurrency and implicit ...
fmontesi's user avatar
  • 171
1 vote
Accepted

Portfolio allocation with a few twists

I'd suggest using integer linear programming (ILP). You need to buy an integer number of stocks, so you can use integer variables to represent the amount of each stock you buy. ILP can express ...
D.W.'s user avatar
  • 162k

Only top scored, non community-wiki answers of a minimum length are eligible