Complexity of min-max subsequence problems

DOI10.1016/S0020-0190(03)00272-2MaRDI QIDQ1014423zbMATH OpenOpenAlexFDO

Authors W. Michiels, J. Korst

Publication date 28 April 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(03)00272-2

zbMATH Keywords

computational complexitypolynomial-time approximation schememin-max subsequence problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Min-max subsequence problems in multi-zone disk recording
• Subsequence Packing: Complexity, Approximation, and Application
• NP-completeness of some optimal sequencing problems with a given grouping of elements
• scientific article; zbMATH DE number 962463
• An optimal algorithm for the two-order multiple problem

Cites work

• Approximation schemes for scheduling on parallel machines
• Cyclic scheduling of offweekends
• Integer Programming with a Fixed Number of Variables
• Min-max subsequence problems in multi-zone disk recording
• Some complexity results about threshold graphs

Cited in

(5)

• The complexity of finding SUBSEQ(A)
• An optimal algorithm for the two-order multiple problem
• Finding the maximum subsequence sum on interconnection networks
• Min-max subsequence problems in multi-zone disk recording
• Optimal sequencing of a set of positive numbers with the variance of the sequence's partial sums maximized

This page was built for publication: Complexity of min-max subsequence problems

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