Reputation
1,874
Next privilege 2,000 Rep.
Edit questions and answers
Badges
9 18
Newest
 Yearling
Impact
~27k people reached

  • 0 posts edited
  • 1 helpful flag
  • 818 votes cast
Feb
1
awarded  Yearling
Dec
30
awarded  Nice Answer
Dec
27
answered List of proofs where existence through probabilistic method has not been constructivised
Oct
27
comment Group Travel Salesman Problem
What are your assumptions on the distances? WIthout any assumptions it is NP-hard to approximate TSP with any polynomial time computable function as approximation factor. For the Euclidean case you might want to look at link.springer.com/chapter/10.1007/11523468_90
Oct
26
comment Group Travel Salesman Problem
The paper Approximation algorithms for the geometric covering salesman problem, Esther M. Arkin and Refael Hassin, Discrete Applied Mathematics 55(3), 197-218 (1994), dx.doi.org/10.1016/0166-218X(94)90008-6 contains approximation results for graphs with geometric structure.
Oct
21
revised On the dependence on $\epsilon$ in Dvoretzky's theorem
added arxiv reference
Oct
21
suggested rejected edit on On the dependence on $\epsilon$ in Dvoretzky's theorem
Oct
21
revised On the dependence on $\epsilon$ in Dvoretzky's theorem
added 240 characters in body
Oct
21
answered On the dependence on $\epsilon$ in Dvoretzky's theorem
Oct
21
answered Two fold optimization: is there an established approach for this kind of problem?
Sep
24
comment Integers in Boxes Problem
The journal version (Average case analysis of greedy algorithms for optimisation problems on set systems, Theoretical Computer Science 145 (1995), 267-298) is available here: basepub.dauphine.fr/xmlui/bitstream/handle/123456789/3978/…
Sep
23
revised Integers in Boxes Problem
added tag co.combinatorics
Sep
22
suggested approved edit on Integers in Boxes Problem
Sep
18
awarded  Enlightened
Sep
18
awarded  Nice Answer
Aug
10
revised Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)
added 120 characters in body
Aug
8
answered Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)
Jul
31
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$.
Jul
31
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