Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph $$G=(V, E)$$ with edge costs $$c \in {\mathbb {R}}_{\ge 0}^E$$ , a root $$r \in V$$ and k terminals $$K\subseteq V$$ , we need to output the minimum-cost arborescence in G that contains an $$r \rightarrow t$$ path for every $$t \in K$$ . Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time $$O(\log ^2k/\log \log k)$$ -approximation Algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound $$d_v$$ on each vertex $$v \in V$$ , and we require that every vertex v in the output tree has at most $$d_v$$ children. We give a quasi-polynomial time $$(O(\log n \log k), O(\log ^2 n))$$ -bicriteria approximation: The Algorithm produces a solution with cost at most $$O(\log n\log k)$$ times the cost of the optimum solution that violates the degree constraints by at most a factor of $$O(\log ^2n)$$ . This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of $$O(\log ^2n)$$ is an $$O(\log n)$$ -factor away from the approximation lower bound of $$\Omega (\log n)$$ from the set-cover hardness. The hardness result holds even on the special case of the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an $$(O(\log n\log k), O(\log n))$$ -bicriteria approximation Algorithm for DB-GST-T.

In this paper we introduce and study the online consistent k-clustering with outliers problem, generalizing the non-outlier version of the problem studied in Lattanzi-Vassilvitskii [18]. We show that a simple local-search based on-line algorithm can give a bicriteria constant approximation for the problem with O(k^2 log^2(nD)) swaps of medians (recourse) in total, where D is the diameter of the metric. When restricted to the problem without outliers, our algorithm is simpler, deterministic and gives better approximation ratio and recourse, compared to that of Lattanzi-Vassilvitskii [18].

We study the online load balancing problem with machine learned predictions, and give results that improve upon and extend those in a recent paper by Lattanzi et al. (2020). First, we design deterministic and randomized online rounding algorithms for the problem in the unrelated machine setting, with $O(\frac{\log m}{\log \log m})$- and $O(\frac{\log \log m}{\log \log \log m})$-competitive ratios. They respectively improve upon the previous ratios of $O(\log m)$ and $O(\log^3\log m)$, and match the lower bounds given by Lattanzi et al. Second, we extend their prediction scheme from the identical machine restricted assignment setting to the unrelated machine setting. With the knowledge of two vectors over machines, a dual vector and a weight vector, we can construct a good fractional assignment online, that can be passed to an online rounding algorithm. Finally, we consider the learning model introduced by Lavastida et al. (2020), and show that under the model, the two vectors can be learned efficiently with a few samples of instances.

Deep Neural Networks (DNNs), despite their tremendous success in recent years, could still cast doubts on their predictions due to the intrinsic uncertainty associated with their learning process. Ensemble techniques and post-hoc calibrations are two types of approaches that have individually shown promise in improving the uncertainty calibration of DNNs. However, the synergistic effect of the two types of methods has not been well explored. In this paper, we propose a truth discovery framework to integrate ensemble-based and post-hoc calibration methods. Using the geometric variance of the ensemble candidates as a good indicator for sample uncertainty, we design an accuracy-preserving truth estimator with provably no accuracy drop. Furthermore, we show that post-hoc calibration can also be enhanced by truth discovery-regularized optimization. On large-scale datasets including CIFAR and ImageNet, our method shows consistent improvement against state-of-the-art calibration approaches on both histogram-based and kernel density-based evaluation metrics. Our code is available at https://github.com/horsepurve/truly-uncertain.

In this paper we study the facility location problem in the online with recourse and dynamic algorithm models. In the online with recourse model, clients arrive one by one and our algorithm needs to maintain good solutions at all time steps with only a few changes to the previously made decisions (called recourse). We show that the classic local search technique can lead to a (1+√2+ε)-competitive online algorithm for facility location with only O(log n/ε log 1/ε) amortized facility and client recourse, where n is the total number of clients arrived during the process. We then turn to the dynamic algorithm model for the problem, where the main goal is to design fast algorithms that maintain good solutions at all time steps. We show that the result for online facility location, combined with the randomized local search technique of Charikar and Guha [Charikar and Guha, 2005], leads to a (1+√2+ε)-approximation dynamic algorithm with total update time of Õ(n²) in the incremental setting against adaptive adversaries. The approximation factor of our algorithm matches the best offline analysis of the classic local search algorithm. Finally, we study the fully dynamic model for facility location, where clients can both arrive and depart. Our main result is an O(1)-approximation algorithm in this model with O(|F|) preprocessing time and O(nlog³ D) total update time for the HST metric spaces, where |F| is the number of potential facility locations. Using the seminal results of Bartal [Bartal, 1996] and Fakcharoenphol, Rao and Talwar [Fakcharoenphol et al., 2003], which show that any arbitrary N-point metric space can be embedded into a distribution over HSTs such that the expected distortion is at most O(log N), we obtain an O(log |F|) approximation with preprocessing time of O(|F|²log |F|) and O(nlog³ D) total update time. The approximation guarantee holds in expectation for every time step of the algorithm, and the result holds in the oblivious adversary model.