Abstract. The polytope scheduling problem (PSP) was introduced by Im, Kulkarni, and Munagala [ J. ACM, 65 (2018), pp. 3:1–3:33] as a very general abstraction of resource allocation over time, where jobs can receive processing rates subject to arbitrary packing constraints. It captures many well-studied problems, including classical unrelated machine scheduling, multidimensional scheduling, and broadcast scheduling. An elegant and well-known algorithm for instantaneous rate allocation with good fairness and efficiency properties is the proportional fairness (PF) algorithm, which was analyzed for PSP by Im, Kulkarni, and Munagala. We drastically improve the analysis of PF for both the general PSP and several of its important special cases subject to the objective of minimizing the sum of weighted completion times. We reduce the upper bound on the competitive ratio from 128 to 27 for general PSP and to 4 for the prominent class of monotone PSP. For certain heterogeneous machine environments, we even close the substantial gap to the lower bound of 2 for nonclairvoyant scheduling. Our analysis also gives the first polynomial-time improvement over the nearly 30-year-old bounds on the competitive ratio of the doubling framework, which was introduced by Hall, Shmoys, and Wein (SODA 1996) for clairvoyant online preemptive scheduling on unrelated machines. Somewhat surprisingly, we achieve this improvement by a nonclairvoyant algorithm, thereby demonstrating that nonclairvoyance is not a (significant) hurdle. Our improvements are based on exploiting monotonicity properties of PSP, providing tight dual fitting arguments on structured instances, and showing new algebraic properties of the optimal objective value for scheduling on unrelated machines. Finally, we establish new connections between PF and matching markets and thereby provide new insights on equilibria and their computational complexity.

The Polytope Scheduling Problem (PSP) was introduced by Im, Kulkarni, and Munagala (JACM 2018) as a very general abstraction of resource allocation over time and captures many well-studied problems including classical unrelated machine scheduling, multidimensional scheduling, and broadcast scheduling. In PSP, jobs with different arrival times receive processing rates that are subject to arbitrary packing constraints. An elegant and well-known algorithm for instantaneous rate allocation with good fairness and efficiency properties is the Proportional Fairness algorithm (PF), which was analyzed for PSP by Im et al.

International audience

Minimizing the sum of weighted completion times on $m$ identical parallel machines is one of the most important and classical scheduling problems. For the stochastic variant where processing times of jobs are random variables, M\"ohring, Schulz, and Uetz (1999) presented the first and still best known approximation result achieving, for arbitrarily many machines, performance ratio $1+\frac12(1+\Delta)$, where $\Delta$ is an upper bound on the squared coefficient of variation of the processing times. We prove performance ratio $1+\frac12(\sqrt{2}-1)(1+\Delta)$ for the same underlying algorithm---the Weighted Shortest Expected Processing Time (WSEPT) rule. For the special case of deterministic scheduling (i.e., $\Delta=0$), our bound matches the tight performance ratio $\frac12(1+\sqrt{2})$ of this algorithm (WSPT rule), derived by Kawaguchi and Kyan in a 1986 landmark paper. We present several further improvements for WSEPT's performance ratio, one of them relying on a carefully refined analysis of WSPT yielding, for every fixed number of machines $m$, WSPT's exact performance ratio of order $\frac12(1+\sqrt{2})-O(1/m^2)$.

BACKGROUND: The identification of functionally or structurally important non-conserved residue sites in protein MSAs is an important challenge for understanding the structural basis and molecular mechanism of protein functions. Despite the rich literature on compensatory mutations as well as sequence conservation analysis for the detection of those important residues, previous methods often rely on classical information-theoretic measures. However, these measures usually do not take into account dis/similarities of amino acids which are likely to be crucial for those residues. In this study, we present a new method, the Quantum Coupled Mutation Finder (QCMF) that incorporates significant dis/similar amino acid pair signals in the prediction of functionally or structurally important sites. RESULTS: The result of this study is twofold. First, using the essential sites of two human proteins, namely epidermal growth factor receptor (EGFR) and glucokinase (GCK), we tested the QCMF-method. The QCMF includes two metrics based on quantum Jensen-Shannon divergence to measure both sequence conservation and compensatory mutations. We found that the QCMF reaches an improved performance in identifying essential sites from MSAs of both proteins with a significantly higher Matthews correlation coefficient (MCC) value in comparison to previous methods. Second, using a data set of 153 proteins, we made a pairwise comparison between QCMF and three conventional methods. This comparison study strongly suggests that QCMF complements the conventional methods for the identification of correlated mutations in MSAs. CONCLUSIONS: QCMF utilizes the notion of entanglement, which is a major resource of quantum information, to model significant dissimilar and similar amino acid pair signals in the detection of functionally or structurally important sites. Our results suggest that on the one hand QCMF significantly outperforms the previous method, which mainly focuses on dissimilar amino acid signals, to detect essential sites in proteins. On the other hand, it is complementary to the existing methods for the identification of correlated mutations. The method of QCMF is computationally intensive. To ensure a feasible computation time of the QCMF's algorithm, we leveraged Compute Unified Device Architecture (CUDA).The QCMF server is freely accessible at http://qcmf.informatik.uni-goettingen.de/.