ﻻ يوجد ملخص باللغة العربية
This paper considers the online machine minimization problem, a basic real time scheduling problem. The setting for this problem consists of n jobs that arrive over time, where each job has a deadline by which it must be completed. The goal is to design an online scheduler that feasibly schedules the jobs on a nearly minimal number of machines. An algorithm is c-machine optimal if the algorithm will feasibly schedule a collection of jobs on cm machines if there exists a feasible schedule on m machines. For over two decades the best known result was a O(log P)-machine optimal algorithm, where P is the ratio of the maximum to minimum job size. In a recent breakthrough, a O(log m)-machine optimal algorithm was given. In this paper, we exponentially improve on this recent result by giving a O(log log m)-machine optimal algorithm.
In the Survivable Network Design problem (SNDP), we are given an undirected graph $G(V,E)$ with costs on edges, along with a connectivity requirement $r(u,v)$ for each pair $u,v$ of vertices. The goal is to find a minimum-cost subset $E^*$ of edges,
Tree comparison metrics have proven to be an invaluable aide in the reconstruction and analysis of phylogenetic (evolutionary) trees. The path-length distance between trees is a particularly attractive measure as it reflects differences in tree shape
The log-concave maximum likelihood estimator (MLE) problem answers: for a set of points $X_1,...X_n in mathbb R^d$, which log-concave density maximizes their likelihood? We present a characterization of the log-concave MLE that leads to an algorithm
For online matching with the line metric, we present a lower bound of $Omega(log n)$ on the approximation ratio of any online (possibly randomized) algorithm. This beats the previous best lower bound of $Omega(sqrt{log n})$ and matches the known upper bound of $O(log n)$.
In population protocols, the underlying distributed network consists of $n$ nodes (or agents), denoted by $V$, and a scheduler that continuously selects uniformly random pairs of nodes to interact. When two nodes interact, their states are updated by