Webster sequences, apportionment problems, and just-in-time sequencing

DOI10.1016/J.DAM.2021.09.020MaRDI QIDQ2243136zbMATH OpenOpenAlexFDO

Authors Xiao-Min Li

Publication date 11 November 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

apportionmentoptimal schedulinginteger sequences

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Special sequences and polynomials (11B83)

Abstract: Given a real number $alphain(0,1)$, we define the Webster sequence of density $alpha$ to be $W_{a}lpha=(lceil(n-1/2)/alphaceil{)}_{ninmathbbN}$, where $lceilxceil$ is the ceiling function. It is known that if $alpha$ and $$ are irrational with $$, then $W_{a}lpha$ and $$ partition $mathbbN$. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of $mathbbN$ into sequences $$ with $$ irrational. In this paper, we consider the question of how close one can come to a three-part partition of $mathbbN$ into Webster sequences with prescribed densities $$. We show that if $$ are irrational with $$, there exists a partition of $mathbbN$ into sequences of densities $$, in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the $n$th element of each sequence in $O(1)$ time and the second algorithm gives the assignment of the $m$th positive integer to a sequence in $O(1)$ time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems.

Recommendations

• Linear-time algorithms for proportional apportionment
• Almost Beatty partitions
• Hybrid Hamilton-Webster and the Greek apportionment
• scientific article; zbMATH DE number 3920153
• Optimal Congressional Apportionment

Cites work

• scientific article; zbMATH DE number 3887801 (Why is no real title available?)
• scientific article; zbMATH DE number 1990000 (Why is no real title available?)
• scientific article; zbMATH DE number 1522554 (Why is no real title available?)
• scientific article; zbMATH DE number 3797865 (Why is no real title available?)
• scientific article; zbMATH DE number 5172390 (Why is no real title available?)
• scientific article; zbMATH DE number 3394238 (Why is no real title available?)
• A Note on the Relation between the Product Rate Variation (PRV) Problem and the Apportionment Problem
• A brief surfey of just-in-time sequencing for mixed-model systems
• A dynamic programming algorithm for scheduling mixed-model, just-in-time production systems
• Almost Beatty partitions
• Asymptotic bias of some election methods
• Asymptotic distribution $\mathrm{mod} m$ and independence of sequences of integers, I
• Balanced sequences and optimal routing
• Complementing and exactly covering sequences
• Covering the positive integers by disjoint sets of the form \(\{[n\alpha+\beta]: n=1,2,\dots \}\)
• Fraenkel's conjecture for six sequences
• Just-in-time scheduling. Models and algorithms for computer and manufacturing systems
• Level Schedules for Mixed-Model Assembly Lines in Just-In-Time Production Systems
• Level Schedules for Mixed-Model, Just-in-Time Processes
• Minimizing variation of production rates in just-in-time systems: A survey
• Note—Sequencing JIT Mixed-Model Assembly Lines
• On A Theorem of Uspensky
• On a distribution problem in finite and countable sets
• On certain distributions of integers in pairs with given differences
• On the chairman assignment problem
• Partitioning the positive integers to seven Beatty sequences
• Proportional Representation
• Proportional optimization and fairness
• The Bracket Function and Complementary Sets of Integers
• The Chairman assignment problem
• The Webster method of apportionment
• The optimality of the online greedy algorithm in carpool and chairman assignment problems
• The probability of the Alabama paradox

Cited in

(1)

• scientific article; zbMATH DE number 5172390 (Why is no real title available?)

This page was built for publication: Webster sequences, apportionment problems, and just-in-time sequencing

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