[math-fun] Packing complexity question
Responses to my MO post http://mathoverflow.net/questions/232165/one-dimensional-packing-of-monomers... haven't taught me anything. Do any of you know (or can any of you figure out) how difficult packing problems of this kind are, from a complexity standpoint? If S is held fixed, then F(n,S) is polynomial time, but that's not very interesting; I want to know what happens as S varies. Jim Propp
On Feb 26, 2016, at 11:09 PM, James Propp <jamespropp@gmail.com> wrote:
Responses to my MO post http://mathoverflow.net/questions/232165/one-dimensional-packing-of-monomers... haven't taught me anything.
Do any of you know (or can any of you figure out) how difficult packing problems of this kind are, from a complexity standpoint?
If S is held fixed, then F(n,S) is polynomial time, but that's not very interesting; I want to know what happens as S varies.
Jim Propp
A natural question, maybe not exactly what you are interested in, is the maximum density of the sequence (n -> infinity) for a given S. That can be calculated by working out a 2^K x 2^K transfer matrix, where K is one greater than the maximum forbidden distance. -Veit
Your problem devolves to finding a maximal independent set in a graph of bounded degree (bounded by the number of forbidden distances). If you Google "independent set bounded degree" you will find various discouraging references. Of course your graphs aren't general bounded-degree graphs, but I doubt there is much leverage in the specific form of your graphs.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of James Propp Sent: Friday, February 26, 2016 11:10 PM To: math-fun Subject: [math-fun] Packing complexity question
Responses to my MO post http://mathoverflow.net/questions/232165/one-dimensional-packing-of- monomers-with-forbidden-distances haven't taught me anything.
Do any of you know (or can any of you figure out) how difficult packing problems of this kind are, from a complexity standpoint?
If S is held fixed, then F(n,S) is polynomial time, but that's not very interesting; I want to know what happens as S varies.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
David Wilson -
James Propp -
Veit Elser