bio  website  

location  Newcastle, Australia  
age  34  
visits  member for  4 years, 6 months 
seen  4 hours ago  
stats  profile views  1,330 
1d

comment 
Is this (funny) combinatorial optimization problem NPhard ? (cutting numbers and placing them in urns)
@user2370336 Yes, your formulation is also valid. My first association was the cutting stock problem, but then I could not see how to really get a connection. The case $C=1$ is also easy. So I'd start thinking about the case $C=2$. Can we cut $m$ sticks of lengths $b_1,\ldots,b_m$ into $2n$ pieces so that the $2n$ pieces come in pairs of equal length (this is equivalent to the lower bound of $(b_1+\cdots+b_m)/2$ being achievable)? 
2d

comment 
Is this (funny) combinatorial optimization problem NPhard ? (cutting numbers and placing them in urns)
The problem can be written as follows: Minimize $\sum_{i=1}^nx_i$ subject to $x_i\geqslant y_{ij}$ for $i\in\{1,\ldots,n\}$, $j\in\{1,\ldots,C\}$, $\sum_{i=1}^n\sum_{j=1}^Cy_{ij}z_{ijk}=b_k$ for $k\in\{1,\ldots,m\}$, $\sum_{k=1}^mz_{ijk}=1$ for $i\in\{1,\ldots,n\}$, $j\in\{1,\ldots,C\}$, $z_{ijk}\in\{0,1\}$ for all $i,j,k$ and $y_{ij}\geqslant 0$ for all $i$, $j$. 
2d

comment 
Is this (funny) combinatorial optimization problem NPhard ? (cutting numbers and placing them in urns)
$(b_1+\cdots+b_m)/C$ is a trivial lower bound. For the given instance this gives 452. Cutting $1100=4\times 275$, $540=3\times 180$ and $170=170$, we can achieve $275+180=455$, which looks optimal to me. 
Jul 24 
revised 
A question of Erdős
added 215 characters in body 
Jul 24 
answered  A question of Erdős 
Jul 21 
answered  Dividing the edges and diagonals of a polygon among disjoint subpolygons 
Jul 8 
revised 
What is known about the complexity of this covering problem?
added 101 characters in body 
Jul 8 
revised 
Maximum cardinality general factor of a graph
added tag co.combinatorics 
Jul 8 
suggested  approved edit on Maximum cardinality general factor of a graph 
Jun 16 
awarded  Organizer 
Jun 16 
revised 
Geometry, Number Theory and Graph Theory of ngon, permutation and graph labeling?
added tag co.combinatorics 
Jun 16 
suggested  approved edit on Geometry, Number Theory and Graph Theory of ngon, permutation and graph labeling? 
Jun 16 
revised 
Geometry, Number Theory and Graph Theory of ngon, permutation and graph labeling?
deleted 63 characters in body 
Jun 16 
revised 
Geometry, Number Theory and Graph Theory of ngon, permutation and graph labeling?
added 396 characters in body 
Jun 16 
revised 
Geometry, Number Theory and Graph Theory of ngon, permutation and graph labeling?
deleted 105 characters in body 
Jun 16 
answered  Geometry, Number Theory and Graph Theory of ngon, permutation and graph labeling? 
May 14 
awarded  Nice Answer 
May 11 
comment 
What is known about the complexity of this covering problem?
@RupeiXu Yes, it means that for every vertex $v\in V\setminus X$ the intersection of $X$ and the neighbourhood of $v$ is either empty or has at least size 2. 
Apr 22 
comment 
What is known about the complexity of this covering problem?
@DominicvanderZypen Yes. I can start the algorithm in the original post with a singleton $S=\{v\}$. If I get stuck then the complement of the final set is a critical set $\neq V$. Now let's do this for every start vertex $v\in V$. If we reach $S=V$ in each case it follows that every vertex is contained in every critical set, and therefore $V$ is the only critical set. 
Apr 21 
comment 
What is known about the complexity of this covering problem?
@DimaPasechnik Note that in order to check feasibility it is not necessary to know all critical sets. The decision version of the problem is in NP, and I've added that to the question. 