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

  • 0 posts edited
  • 2 helpful flags
  • 853 votes cast
Mar
22
comment Cases of equality in Daykin's theorem
You might want to have a look at the paper Towards characterizing equality in correlation inequalities by Ahlswede and Khachatrian, Europ. J. Combinatorics 16 (1995), dx.doi.org/10.1016/0195-6698(95)90015-2
Mar
9
answered Generalizing series-parallel digraphs with feedback
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$.