Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOne (more) line on the most Ancient Algorithm in History
68
0
0.0
(
0
)
Added by
Ilya Volkovich
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give a new simple and short (one-line) analysis for the runtime of the well-known Euclidean Algorithm. While very short simple, the obtained upper bound in near-optimal.
rate research
Read More
Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled the greedy algorithm is optimal for on-line edge coloring, shows that the competitive ratio of $2$ of the naive greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree $Delta = O(log n)$, which prompted them to conjecture that better bounds are possible for higher-degree graphs. While progress has been made towards resolving this conjecture for restricted inputs and arrivals or for random arrival orders, an answer for fully general emph{adversarial} arrivals remained elusive. We resolve this thirty-year-old conjecture in the affirmative, presenting a $(1.9+o(1))$-competitive online edge coloring algorithm for general graphs of degree $Delta = omega(log n)$ under vertex arrivals. At the core of our results, and of possible independent interest, is a new online algorithm which rounds a fractional bipartite matching $x$ online under vertex arrivals, guaranteeing that each edge $e$ is matched with probability $(1/2+c)cdot x_e$, for a constant $c>0.027$.
In this paper, we introduce the on-line Viterbi algorithm for decoding hidden Markov models (HMMs) in much smaller than linear space. Our analysis on two-state HMMs suggests that the expected maximum memory used to decode sequence of length $n$ with
$m$-state HMM can be as low as $Theta(mlog n)$, without a significant slow-down compared to the classical Viterbi algorithm. Classical Viterbi algorithm requires $O(mn)$ space, which is impractical for analysis of long DNA sequences (such as complete human genome chromosomes) and for continuous data streams. We also experimentally demonstrate the performance of the on-line Viterbi algorithm on a simple HMM for gene finding on both simulated and real DNA sequences.
We have determined the detailed star formation history and total mass of the globular clusters in the Fornax dwarf spheroidal using archival HST WFPC2 data. Colour magnitude diagrams are constructed in the F555W and F814W bands and corrected for the effect of Fornax field star contamination, after which we use the routine Talos to derive the quantitative star formation history as a function of age and metallicity. The star formation history of the Fornax globular clusters shows that Fornax 1, 2, 3 and 5 are all dominated by ancient (>10 Gyr) populations. Cluster Fornax 1,2 and 3 display metallicities as low as [Fe/H]=-2.5 while Fornax 5 is slightly more metal-rich at [Fe/H]=-1.8, consistent with resolved and unresolved metallicity tracers. Conversely, Fornax 4 is dominated by a more metal-rich~([Fe/H]=-1.2) and younger population at 10 Gyr, inconsistent with the other clusters. A lack of stellar populations overlapping with the main body of Fornax argues against the nucleus cluster scenario for Fornax 4. The combined stellar mass in globular clusters as derived from the SFH is (9.57$pm$0.93)$times$10$^{5}$ M$_{odot}$ which corresponds to 2.5$pm$0.2 percent of the total stellar mass in Fornax. The mass of the four most metal-poor clusters can be further compared to the metal-poor Fornax field to yield a mass fraction of 19.6$pm$3.1 percent. Therefore, the SFH results provide separate supporting evidence for the unusually high mass fraction of the GCs compared to the Fornax field population.
We study the multistage $K$-facility reallocation problem on the real line, where we maintain $K$ facility locations over $T$ stages, based on the stage-dependent locations of $n$ agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. $K$-facility reallocation was introduced by de Keijzer and Wojtczak, where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider online $K$-facility reallocation, where the algorithm becomes aware of agent locations in a stage-by-stage fashion. By exploiting an interesting connection to the classical $K$-server problem, we present a constant-competitive algorithm for $K = 2$ facilities.
We use gravitational lensing of the cosmic microwave background (CMB) to measure the mass of the most distant blindly-selected sample of galaxy clusters on which a lensing measurement has been performed to date. In CMB data from the the Atacama Cosmology Telescope (ACT) and the Planck satellite, we detect the stacked lensing effect from 677 near-infrared-selected galaxy clusters from the Massive and Distant Clusters of WISE Survey (MaDCoWS), which have a mean redshift of $ langle z rangle = 1.08$. There are no current optical weak lensing measurements of clusters that match the distance and average mass of this sample. We detect the lensing signal with a significance of $4.2 sigma$. We model the signal with a halo model framework to find the mean mass of the population from which these clusters are drawn. Assuming that the clusters follow Navarro-Frenk-White density profiles, we infer a mean mass of $langle M_{500c}rangle = left(1.7 pm 0.4 right)times10^{14},mathrm{M}_odot$. We consider systematic uncertainties from cluster redshift errors, centering errors, and the shape of the NFW profile. These are all smaller than 30% of our reported uncertainty. This work highlights the potential of CMB lensing to enable cosmological constraints from the abundance of distant clusters populating ever larger volumes of the observable Universe, beyond the capabilities of optical weak lensing measurements.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
