Search for: All records

The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison. The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case.This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online. This models the case in practice where yesterday's data is available and is similar to today's online instance. This sample is drawn from a known distribution which may not be uniform. We design an online algorithm with strong theoretical guarantees. The algorithm has a small constant competitive ratio when the sample is uniform---if not, we show we can recover the same result by adding a provably minimal sample. Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results. 

Abstract Ionospheric day‐to‐day variability is ubiquitous, even under undisturbed geomagnetic and solar conditions. In this paper, quiet‐time day‐to‐day variability of equatorial vertical E × B drift is investigated using observations from ROCSAT‐1 satellite and the Whole Atmosphere Community Climate Model with thermosphere and ionosphere eXtension (WACCM‐X) v2.1 simulations. Both observations and model simulations illustrate that the day‐to‐day variability reaches the maximum at dawn, and the variability of dawn drift is largest around June solstice at ~90–180°W. However, there are significant challenges to reproduce the observed magnitude of the variability and the longitude distributions at other seasons. Using a standalone electro‐dynamo model, we find that the day‐to‐day variability of neutral winds in the E‐region (≤~130 km) is the primary driver of the day‐to‐day variability of dawn drift. Ionospheric conductivity modulates the drift variability responses to the E‐region wind variability, thereby determining its strength as well as its seasonal and longitudinal variations. Further, the day‐to‐day variability of dawn drift induced by individual tidal components of winds in June are examined: DW1, SW2, D0, and SW1 are the most important contributors.