Discussion Locked

Management of NP-completeness Project

0 helpful
1 reply
Closed to new repliesThis discussion is closed. It stays readable, but it takes no new replies.

Although many software engineering projects just involve in SELECT/INSERT/UPDATE/DELETE data in databases or performing steps one by one with some loops, there are some projects involving NP-completeness problems, which mean no polynomial algorithm to be solved.

For example, paper optimization in printing industry is a usual problem. Maximizing the number of same polygons (from rectangles to irregular shapes) packed on a piece of rectangle paper which dimension is given.

The problems of handling this kind of project include
1. Optimization cannot be archieved by simple programming.
2. Difficult problems lie on much smart System analysts and programmers.
3. Schedule should include the period of research and development both, which are difficult to be estimated
4. UAT would include testing the optimization. If your algorithm cannot achieve the defined optimization, the project will fail.
5. This kind of project is usually tailor-made. Highly customization reduces the system'sreusability. The cost of this project would be much higher than that of others.
6. Usually the problem could be solved by some masters of such industries manually, they have expectation that the product would be as best as their methods are. Since their methods might not be polynomial algorithm, you have to seek alternative to implement. But different methods archieving the same result is a large difficulty.

On the other hand, such kind of projects is very valuable and sold at very high price. The question is

"How can we take this sweet fruit from the sky-high tree?"

1 reply

by areets

Using endogenous to exogenous nonparametric regressive polynomial algorithms.

Based on my small collection of research material in this area, Sigma_2^P = NP^NP from Huynh and Tian was studied and a paper created by Yoram Hirshfeld, Mark Jerrum and Faron Moller which they dedicated to Robin Milner.

Their polynomial-time algorithm using NP questions, can resolve NP-completeness problems.

Local Polynomial Fitting with Long-Memory and Antipersistent errors, which retain a corollary viewof anti persistence errors, can be added to the computation sequence.

A Polynomial Algorithm for Special Case of the One-Machine Scheduling Problem with Time-Lags converging the above algorithms into a ?New? algorithm to resolve both NP- and polynomial completeness errors.

The companies in these industries should use universities and their self-initiated R&D programmes to bring ?this sweet fruit from the sky-high tree?.

K=Industry
S=Computation
E=Business

TSP

This discussion is closed to new replies.