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 (2010)
- Volume: 30, Issue: 2, page 191-203
- ISSN: 1509-9407
Access Full Article
top
Abstract
topHow to cite
topStanisław Gawiejnowicz, Wiesław Kurc, and Lidia Pankowska. "Solving a permutation problem by a fully polynomial-time approximation scheme." Discussiones Mathematicae, Differential Inclusions, Control and Optimization 30.2 (2010): 191-203. <http://eudml.org/doc/271198>.
@article{StanisławGawiejnowicz2010,
abstract = {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.},
author = {Stanisław Gawiejnowicz, Wiesław Kurc, Lidia Pankowska},
journal = {Discussiones Mathematicae, Differential Inclusions, Control and Optimization},
keywords = {combinatorial optimization; discrete control theory; fully polynomial-time approximation scheme; polynomial-time approximation scheme},
language = {eng},
number = {2},
pages = {191-203},
title = {Solving a permutation problem by a fully polynomial-time approximation scheme},
url = {http://eudml.org/doc/271198},
volume = {30},
year = {2010},
}
TY - JOUR
AU - Stanisław Gawiejnowicz
AU - Wiesław Kurc
AU - Lidia Pankowska
TI - Solving a permutation problem by a fully polynomial-time approximation scheme
JO - Discussiones Mathematicae, Differential Inclusions, Control and Optimization
PY - 2010
VL - 30
IS - 2
SP - 191
EP - 203
AB - 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.
LA - eng
KW - combinatorial optimization; discrete control theory; fully polynomial-time approximation scheme; polynomial-time approximation scheme
UR - http://eudml.org/doc/271198
ER -
References
top- [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. Zbl1057.68547
- [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 Zbl1113.90059
- [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 Zbl0345.90049
- [5] G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Research 39 (1991), 979-991. doi: 10.1287/opre.39.6.979 Zbl0748.90033
- [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
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.