Questions Tagged With complexityhttp://www.or-exchange.com/tags/complexity/?type=rssquestions tagged <span class="tag">complexity</span>enTue, 07 May 2013 14:33:30 -0400[ANN] An interesting site on algorithmic complexityhttp://www.or-exchange.com/questions/7951/ann-an-interesting-site-on-algorithmic-complexity<p>The website <a href="http://bigocheatsheet.com/"></a><a href="http://bigocheatsheet.com/">http://bigocheatsheet.com/</a> has a big collection of lot of commonly used algorithms and their time complexity. Recently came across this site and thought it might an interesting resource for this community.
I am not related to this site.</p>Samik R.Tue, 07 May 2013 14:33:30 -0400http://www.or-exchange.com/questions/7951/ann-an-interesting-site-on-algorithmic-complexitycomplexityalgorithmsTime complexity of a non-linear modelhttp://www.or-exchange.com/questions/5192/time-complexity-of-a-non-linear-model<p>Hello
I have faced a non-linear problem in my modeling. My model is as follows:
max sum {x_i}
s.t.
x_i.y_i=z_i 1<i<n
....
some linear constrains</p>
<p>In this models, x_i, y_i, and z_i are continuous variables for {1<i<n}. As you can see we have a product term in constrains. My question is if this problem is P or NP? I strongly think it is NP. This is because the I found that the product term can be approximated by peicewise linear optimization techniques ("AIMMS Optimization Modeling" ebook, chapter 7, <a href="http://www.aimms.com/downloads/manuals/optimization-modeling">http://www.aimms.com/downloads/manuals/optimization-modeling</a> ). This method convert the constrain to a MILP form, which is NP-hard. But this proof is not precise. So, I would like to ask if anyone can help me on this topic.
Thanks<br>
</p>jamedadiSun, 01 Apr 2012 15:33:00 -0400http://www.or-exchange.com/questions/5192/time-complexity-of-a-non-linear-modelcomplexitynp-hardnon-lineartimeSpeed of max-flow algorithms when max known in advance?http://www.or-exchange.com/questions/4335/speed-of-max-flow-algorithms-when-max-known-in-advance<p>I have a generalized flow network. I want to maximize the flow to the sink, and the flow along each arc must be integral (all capacities and gains are integral). If I know, in advance, the value of the max flow to the sink (but not the routes through the network), does this in any way speed up any algorithms usually used to solve this problem? If so, what would this speed up be (in terms of Big-O notation)?</p>OR_MRTue, 03 Jan 2012 21:57:25 -0500http://www.or-exchange.com/questions/4335/speed-of-max-flow-algorithms-when-max-known-in-advancecomplexitynetworksIs there any simple optimization problem example which is not in class NP?http://www.or-exchange.com/questions/841/is-there-any-simple-optimization-problem-example-which-is-not-in-class-np<p>The first step of an NP-completeness proof for a problem B is that we show B is in class NP:
i) B can be solved in polynomial time with a nondeterministic turing machine
or equivalently
ii) There exists a polynomial time "verifier" for the problem that is for a given candidate solution we can decide "YES/NO" in polynomial time. </p>
<p>I couldn’t find any simple optimization problem example which is not in NP.
There are some weird examples (Halting Problem), but I am wondering whether there exist any optimization problem example?</p>ArmanSat, 23 Oct 2010 10:39:27 -0400http://www.or-exchange.com/questions/841/is-there-any-simple-optimization-problem-example-which-is-not-in-class-npcomplexityWhy can't we solve longest path problem by using shortest path algoritms?http://www.or-exchange.com/questions/823/why-cant-we-solve-longest-path-problem-by-using-shortest-path-algoritms<p>Consider a maximization problem of a function f(x) on a feasible set S.
We know that the following problem is equivalent to the problem above: min -f(x) on S.</p>
<p>Now, suppose that we want to solve a longest path problem instance on a network (possibly containing some cycles).
Since shortest path problem is solvable in polynomial time, one can do the following
multiply all arc weights by -1 to make it a shortest path problem instance and solve it by Bellman's algorithm to get a solution which is equivalent to solve longest path problem instance due to the statement in the first paragraph since we only multiplied all the coefficients of the objective function by -1.
However, the longest path problem is NP-hard, so I know that this should not work but why? </p>
<p>Maybe the answer is obvious but I could not figure this out.</p>
<p>Thank you.</p>ArmanMon, 18 Oct 2010 19:33:53 -0400http://www.or-exchange.com/questions/823/why-cant-we-solve-longest-path-problem-by-using-shortest-path-algoritmscomplexityoptimizationComplexity results for classical OR problemshttp://www.or-exchange.com/questions/754/complexity-results-for-classical-or-problems<p>I'm looking for [concise, yet comprehensive] online resources and/or (state of the art) survey papers presenting complexity results for classical OR problems such as</p>
<ul>
<li>Shortest Path and Spanning Tree Problems;</li>
<li>Network Flow, Assignment and Knapsack Problems;</li>
<li>Traveling Salesman and Vehicle Routing Problems;</li>
<li>...</li>
</ul>
<p>(and their respective variants).</p>
<p>By "complexity results", both problem-specific lower bounds (resp., complexity classes) as well as performance of seminal algorithms (optimal, approximative) should be addressed.</p>
<p>For instance, the <a href="http://www.lix.polytechnique.fr/~durr/query/">Scheduling Zoo</a> is a nice searchable bibliography on results w.r.t. scheduling problems (though, it does not offer detailed statements in terms of Big-\(O\)-assessments).</p>
<hr>
<p><strong><em>Collected web resources:</em></strong></p>
<ul>
<li><a href="http://qwiki.stanford.edu/index.php/Complexity_Garden">Complexity Garden</a> <em>(w.i.p.)</em></li>
<li><a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations">Computational complexity of mathematical operations</a></li>
<li>
<p><a href="http://bigocheatsheet.com/">Big-O Algorithm Complexity Cheat Sheet</a></p>
</li>
<li>
<p><a href="http://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms">Shortest Path Problems</a></p>
</li>
</ul>
<ul>
<li>Assignment Problems</li>
<ul>
<li>Quadratic Assignment Problem</li>
<ul>
<li><a href="http://www.seas.upenn.edu/qaplib/">QAPLIB - A Quadratic Assignment Problem Library</a></li>
</ul>
</ul>
</ul>
<ul>
<li>Network Flow Problems</li>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Maximum_flow_problem#Solutions">Maximum Flow Problem</a></li>
</ul>
</ul>
<ul>
<li>
<p><a href="http://www.tsp.gatech.edu/">Traveling Salesman Problems</a></p>
</li>
<li>
<p><a href="http://neo.lcc.uma.es/radi-aeb/WebVRP/">Vehicle Routing Problems</a></p>
</li>
</ul>
<ul>
<li>Scheduling Problems</li>
<ul>
<li><a href="http://www.informatik.uni-osnabrueck.de/knust/class/">Complexity results for scheduling problems</a></li>
<ul>
<li><a href="http://www.lix.polytechnique.fr/~durr/query/">The scheduling zoo — A searchable bibliography</a></li>
</ul>
</ul>
</ul>
<hr>
<p>PS: This is a "community question". Feel free to edit as needed. (That is, if you have at least 30 "karma points".)</p>fbahrWed, 29 Sep 2010 19:47:15 -0400http://www.or-exchange.com/questions/754/complexity-results-for-classical-or-problemscomplexityalgorithmscommunity-wikiNew Proof that P!=NPhttp://www.or-exchange.com/questions/623/new-proof-that-pnp<p>So, has anyone been following this new claim on a proof? I recall a thread on sci.op-research from a few days back. Obviously, it's natural to be skeptical after all the cranks who pop up at regular intervals, but the guy in question seems like a serious researcher. It's even been covered in today's New York Times: <a href="http://www.nytimes.com/2010/08/17/science/17proof.html?ref=technology" rel="nofollow">http://www.nytimes.com/2010/08/17/science/17proof.html?ref=technology</a>. Although that's not a claim to fame, perhaps!</p>
<p>Complexity is not one of my areas, but perhaps someone who works in the field can shed some light on whether this will go anywhere...</p>Jay RajgopalTue, 17 Aug 2010 20:01:53 -0400http://www.or-exchange.com/questions/623/new-proof-that-pnpcomplexityDoes cellular automaton have any kind of real life application?http://www.or-exchange.com/questions/332/does-cellular-automaton-have-any-kind-of-real-life-application<p>I watched Stephen Wolfram's <a href="http://www.youtube.com/watch?v=60P7717-XOQ" rel="nofollow">TED Talk</a> and although I enjoyed it, I have a hard time finding any relationship between his "New Kind of Science" and the reality. I understand that his cellular automaton may be used in random number generation (although reported to perform poorly) but I am wondering if there are other applications for it. </p>
<p>And as far as I can understand some of his rules are Turing Complete. Does it mean that by studying these we can better understand the complexity theory? </p>
<p>If you have read his book, do you recommend it?</p>
<p>Update:</p>
<ul>
<li><a href="http://www.cscs.umich.edu/~crshalizi/reviews/wolfram/" rel="nofollow">Here is</a> a review of Worlfram's work</li>
</ul>MarkFri, 30 Apr 2010 08:36:06 -0400http://www.or-exchange.com/questions/332/does-cellular-automaton-have-any-kind-of-real-life-applicationcomplexity