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

DOI10.7151/DMDICO.1119MaRDI QIDQ3000079zbMATH OpenOpenAlexFDO

Authors Stanisław Gawiejnowicz, Wiesław Kurc, Lidia Pankowska

Publication date 18 May 2011

Published in Discussiones Mathematicae. Differential Inclusions, Control and Optimization (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/4d241f5af77fdfee7ef10de89672a91767562c2b

zbMATH Keywords

combinatorial optimizationdiscrete control theorypolynomial-time approximation scheme

Mathematics Subject Classification ID

Linear optimal control problems (49N05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Combinatorial optimization (90C27)

Recommendations

• On exact algorithms for the permutation CSP
• A space-time tradeoff for permutation problems
• A solution to one of Knuth's permutation problems
• A polynomial time solution for permutation scaffold filling
• An \(O(n^2)\) time algorithm for the minimal permutation completion problem
• An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
• Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• scientific article; zbMATH DE number 1617282

Cited in

(4)

• Solving static permutation mastermind using \(O(n \log n)\) queries
• Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
• scientific article; zbMATH DE number 177149 (Why is no real title available?)
• Partial dominated schedules and minimizing the total completion time of deteriorating jobs

This page was built for publication: Solving a permutation problem by a fully polynomial-time approximation scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000079)