Optimal sequencing of a set of positive numbers with the variance of the sequence's partial sums maximized

DOI10.1007/S11590-012-0449-9MaRDI QIDQ360482zbMATH OpenOpenAlexFDO

Authors Li Wei, Wangdong Qi, Dingxing Chen, En Yuan, Peng Liu

Publication date 27 August 2013

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.2410

zbMATH Keywords

optimal sequencepartial sumssequencingvariance

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Abstract: We consider the problem of sequencing a set of positive numbers. We try to find the optimal sequence to maximize the variance of its partial sums. The optimal sequence is shown to have a beautiful structure. It is interesting to note that the symmetric problem which aims at minimizing the variance of the same partial sums is proved to be NP-complete in the literature.

Recommendations

• Complexity of min-max subsequence problems
• scientific article; zbMATH DE number 1472145
• Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem
• An Algorithm for the Determination of the Variance of a Partially Ordered Set
• Optimal Partitioning of Sequences

Cites work

• A branch and bound algorithm to minimize completion time variance on a single processor.
• Batch scheduling and common due-date assignment on a single machine
• Completion time variance minimization on a single machine is difficult
• Job scheduling methods for reducing waiting time variance
• Minimising Waiting Time Variance in the Single Machine Problem
• Minimizing the Time-in-System Variance for a Finite Jobset
• Proof of a conjecture of Schrage about the completion time variance problem
• Variance Minimization in Single Machine Sequencing Problems

Cited in

(4)

• Another well-solvable case of the QAP: maximizing the job completion time variance
• Linear programming insights into solvable cases of the quadratic assignment problem
• Maximizing the sum of integers when their sum of squares is fixed
• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence

This page was built for publication: Optimal sequencing of a set of positive numbers with the variance of the sequence's partial sums maximized

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