Solving a permutation problem by a fully polynomial-time approximation scheme

• Autorzy: Stanisław Gawiejnowicz , Wiesław Kurc , Lidia Pankowska
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

combinatorial optimization; discrete control theory; fully polynomial-time approximation scheme

Kategorie tematyczne

• 68M20: Performance evaluation; queueing; scheduling
• 49N05: Linear optimal control problems
• 90C27: Combinatorial optimization

• Wydawca: Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra
• Czasopismo: Discussiones Mathematicae, Differential Inclusions, Control and Optimization
• Rocznik: 2010
• Tom: 30
• Numer: 2
• Strony: 191-203

Daty

wydano

2010

otrzymano

2009-11-30

Twórcy

autor

Stanisław Gawiejnowicz

• Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Poland

autor

Wiesław Kurc

• Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Poland

autor

Lidia Pankowska

• Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Poland

Bibliografia

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

Identyfikatory

DOI

10.7151/dmdico.1119