All Questions
15
questions
2
votes
0
answers
41
views
Dividing $N$ coins into at most $K$ groups such that I can get any number of coins by selecting whole groups
Problem
Inspired from Dividing $100$ coins into $7$ groups such that I can choose any number of coins by selecting whole groups . I am interested in the number of possible ways we can get such a split....
- 1,171
2
votes
0
answers
73
views
Bin packing : item to be packed in a certain bin depend on previously packed items to that bin.
I am working on an engineering problem. I need to implement an algorithm that looks like a certain variant of bin packing. Specifically, in this variant of the bin packing, the size of a certain item ...
- 131
2
votes
2
answers
86
views
Is this problem NP-hard？Or what kind of mathematical problem does it belong to?
Assuming there are n types of gifts, each with a number of $a_n$. Now we have to pack them into gift packs, each containing several types of gifts, and each gift has only one.If a gift package ...
- 33
2
votes
0
answers
17
views
Mechanic shop with limited delay capacity
Suppose a mechanic shop serves $M$ customers for $N$ days. Each morning, each customer brings in a number of parts to repair (denoted by $0\leq A_{i,j}\leq A_{max}$).
Suppose all parts need to be ...
- 75
0
votes
1
answer
50
views
Checking NP-completeness of the following problem(s)- Assigning candidates to departments
Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. Suppose each department $d$ is considering hiring some $C_d \subseteq \{1, 2, ... n\}$ candidates (...
- 1
0
votes
0
answers
160
views
NP completeness of a variant of assignment problem
I have the following variant of assignment problem:
Suppose we have $m$ machines and $n$ jobs. Each machine is capable of doing a subset of jobs and each machine $i$ has capacity $C_i$. Each job $j$ ...
- 422
1
vote
0
answers
11
views
Find Extremal Point over a Set of all Simple Cycle in a Directed Graph
Dearl all,
I recently stumbled across an interesting combinatorial problem and was wondering if someone here has faced something similar and would help me get a head start.
Problem Defintion
Let G be ...
- 11
0
votes
1
answer
136
views
Knapsack problem on 2D or 3D space
Considering a series of rectangle items with known size $(a_1,b_1),(a_2,b_2)\cdots,(a_n,b_n)$, and a big rectangle box with size $(A,B)$
Question 1: How to fill the box with the items that minimize ...
0
votes
1
answer
107
views
Is the generalized assignment problem with un-capacitated agents NP-hard?
I am working on a generalized assignment problem which I typed below. I know it is shown to be NP-hard. I am wondering whether the problem is still NP-hard when the capacity of the agents are assumed ...
8
votes
2
answers
2k
views
Minimum transactions to settle debts among friends
You are given $n$ integers $x_1,x_2,\dots,x_n$ satisfying $\sum_{i=1}^n x_i=0$. A legal move is to choose an integer $a$ and two indices $i,j$, and to increase $x_i$ by $a$ and decrease $x_j$ by $a$. ...
- 98
0
votes
2
answers
467
views
Division n items into k boxes prove that it is NP-Complete
I don't know how to solve this problem. Can anyone help me with it please? I need to prove that this is a NP-complete problem.
We are given $n$ items with sizes $s_1, s_2, ... ,s_n$, where $0 < ...
- 31
3
votes
1
answer
166
views
NP-complete impossible to solve in $O(n)$
NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small $d$?...
- 265
1
vote
1
answer
68
views
Questions concerning assumptions to conclude that $\operatorname{P}=\operatorname{NP}$
Suppose you find a reduction from the $k$-vertex-cut problem to the
hamiltonian-path problem. In particular, you find an algorithm $A$
that, given the graph $G$ and the number $k$, outputs a graph ...
- 11
2
votes
1
answer
2k
views
How can we show that 3-dimensional matching $\le_p$ exact cover?
In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
- 215
4
votes
3
answers
1k
views
Using up letters on a refrigerator is NP-complete
You spend some time with your preschool-age daughter trying to use up all of the magnet letters on the refrigerator to spell words that she knows. Formally, you have a set of letters and you are ...
- 61