1,702 reputation
716
bio website
location Newcastle, Australia
age 34
visits member for 4 years, 6 months
seen 4 hours ago

1d
comment Is this (funny) combinatorial optimization problem NP-hard ? (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 NP-hard ? (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 NP-hard ? (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 sub-polygons
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 n-gon, permutation and graph labeling?
added tag co.combinatorics
Jun
16
suggested approved edit on Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
Jun
16
revised Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
deleted 63 characters in body
Jun
16
revised Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
added 396 characters in body
Jun
16
revised Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
deleted 105 characters in body
Jun
16
answered Geometry, Number Theory and Graph Theory of n-gon, 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.