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

DOI10.1007/S11590-012-0449-9zbMATH Open1300.90051arXiv1202.2410OpenAlexW3105170761MaRDI QIDQ360482FDOQ360482

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)

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.

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

Recommendations

• Complexity of min-max subsequence problems
• Publication:4489196
• 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

zbMATH Keywords

variancepartial sumssequencingoptimal sequence

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Cites Work

• Completion time variance minimization on a single machine is difficult
• Variance Minimization in Single Machine Sequencing Problems
• Proof of a conjecture of Schrage about the completion time variance problem
• 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
• Minimizing the Time-in-System Variance for a Finite Jobset
• Minimising Waiting Time Variance in the Single Machine Problem
• Job scheduling methods for reducing waiting time variance

Cited In (4)

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

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)