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. 

We extend the algebraic K-stability theory to projective klt pairs with a biganticanonical class. While in general such a pair could behave pathologically,it is observed in this note that K-semistability condition will force them tohave a klt anticanonical model, whose stability property is the same as theoriginal pair. 

We extend the algebraic K-stability theory to projective klt pairs with a big anticanonical class. While in general such a pair could behave pathologically, it is observed in this note that the K-semistability condition will force them to have a klt anticanonical model, whose stability property is the same as that of the original pair. 

Abstract We prove an algebraic version of the Hamilton–Tian conjecture for all log Fano pairs. More precisely, we show that any log Fano pair admits a canonical two-step degeneration to a reduced uniformly Ding stable triple, which admits a Kähler–Ricci soliton when the ground field . 

This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm’s worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms’ performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.