Solving a permutation problem by a fully polynomial-time approximation scheme
Stanisław Gawiejnowicz ; Wiesław Kurc ; Lidia Pankowska
Discussiones Mathematicae, Differential Inclusions, Control and Optimization, Tome 30 (2010), p. 191-203 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

For a problem of optimal discrete control with a discrete control set composed of vertices of an n-dimensional permutohedron, a fully polynomial-time approximation scheme is proposed.

Publié le : 2010-01-01
EUDML-ID : urn:eudml:doc:271198 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmdico_1119,
     author = {Stanis\l aw Gawiejnowicz and Wies\l aw Kurc and Lidia Pankowska},
     title = {Solving a permutation problem by a fully polynomial-time approximation scheme},
     journal = {Discussiones Mathematicae, Differential Inclusions, Control and Optimization},
     volume = {30},
     year = {2010},
     pages = {191-203},
     zbl = {1225.90105},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmdico_1119}
}

Stanisław Gawiejnowicz; Wiesław Kurc; Lidia Pankowska. Solving a permutation problem by a fully polynomial-time approximation scheme. Discussiones Mathematicae, Differential Inclusions, Control and Optimization, Tome 30 (2010) pp. 191-203. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmdico_1119/

[000] [1] S. Gawiejnowicz, Time-Dependent Scheduling, Monographs in Theoretical Computer Science: An EATCS Series (Springer, 2008).

[001] [2] S. Gawiejnowicz, W. Kurc and L. Pankowska, A greedy approach for a time-dependent scheduling problem, Lecture Notes in Computer Science 2328 (2002), 79-86. | Zbl 1057.68547

[002] [3] S. Gawiejnowicz, W. Kurc and L. Pankowska, Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences, Discrete Appl. Math. 154 (2006), 2150-2166. doi: 10.1016/j.dam.2005.04.016 | Zbl 1113.90059

[003] [4] O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems, Journal of ACM 22 (1975), 463-468. doi: 10.1145/321906.321909 | Zbl 0345.90049

[004] [5] G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Research 39 (1991), 979-991. doi: 10.1287/opre.39.6.979 | Zbl 0748.90033

[005] [6] G. Woeginger, When does a dynamic programming formulation guarantee the existence of an FPTAS? INFORMS Journal on Computing 12 (2000), 57-73. doi: 10.1287/ijoc.12.1.57.11901