Search for: All records

In the submodular ranking (SR) problem, the input consists of a set of submodular functions defined on a ground set of elements. The goal is to order elements for all the functions to have value above a certain threshold as soon on average as possible, assuming we choose one element per time. The problem is flexible enough to capture various applications in machine learning, including decision trees. This paper considers the min-max version of SR where multiple instances share the ground set. With the view of each instance being associated with an agent, the min-max problem is to order the common elements to minimize the maximum objective of all agents---thus, finding a fair solution for all agents. We give approximation algorithms for this problem and demonstrate their effectiveness in the application of finding a decision tree for multiple agents.

 

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. 

We prove two new results on the K K -polystability of Q \mathbb {Q} -Fano varieties based on purely algebro-geometric arguments. The first one says that any K K -semistable log Fano cone has a special degeneration to a uniquely determined K K -polystable log Fano cone. As a corollary, we combine it with the differential-geometric results to complete the proof of Donaldson-Sun’s conjecture which says that the metric tangent cone of any point appearing on a Gromov-Hausdorff limit of Kähler-Einstein Fano manifolds depends only on the algebraic structure of the singularity. The second result says that for any log Fano variety with the torus action, K K -polystability is equivalent to equivariant K K -polystability, that is, to check K K -polystability, it is sufficient to check special test configurations which are equivariant under the torus action.