Geodesic
Solving a permutation problem by a fully polynomial-time approximation scheme
Discussiones Mathematicae. Differential Inclusions, Control and Optimization, Tome 30 (2010) no. 2, pp. 191-203 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: combinatorial optimization, discrete control theory, fully polynomial-time approximation scheme 
@article{DMDICO_2010_30_2_a1,
     author = {Gawiejnowicz, Stanis{\l}aw and Kurc, Wies{\l}aw and Pankowska, Lidia},
     title = {Solving a permutation problem by a fully polynomial-time approximation scheme},
     journal = {Discussiones Mathematicae. Differential Inclusions, Control and Optimization},
     pages = {191--203},
     year = {2010},
     volume = {30},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMDICO_2010_30_2_a1/}
}
TY  - JOUR
AU  - Gawiejnowicz, Stanisław
AU  - Kurc, Wiesław
AU  - Pankowska, Lidia
TI  - Solving a permutation problem by a fully polynomial-time approximation scheme
JO  - Discussiones Mathematicae. Differential Inclusions, Control and Optimization
PY  - 2010
SP  - 191
EP  - 203
VL  - 30
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMDICO_2010_30_2_a1/
LA  - en
ID  - DMDICO_2010_30_2_a1
ER  - 
%0 Journal Article
%A Gawiejnowicz, Stanisław
%A Kurc, Wiesław
%A Pankowska, Lidia
%T Solving a permutation problem by a fully polynomial-time approximation scheme
%J Discussiones Mathematicae. Differential Inclusions, Control and Optimization
%D 2010
%P 191-203
%V 30
%N 2
%U http://geodesic.mathdoc.fr/item/DMDICO_2010_30_2_a1/
%G en
%F DMDICO_2010_30_2_a1
Gawiejnowicz, Stanisław; Kurc, Wiesław; Pankowska, Lidia. Solving a permutation problem by a fully polynomial-time approximation scheme. Discussiones Mathematicae. Differential Inclusions, Control and Optimization, Tome 30 (2010) no. 2, pp. 191-203. http://geodesic.mathdoc.fr/item/DMDICO_2010_30_2_a1/

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

[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.

[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

[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

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

[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