We consider Buy-at-Bulk Network Design with Protection, which is motivated by fault-tolerance in high speed (optical) networks. Given a graph G=(V,E) and a set of demand pairs (s1,t1), …,(sr,tr), the goal is to route a demand of δ(i) for each pair (si,ti) along two internally vertex-disjoint paths (to protect against a vertex failure) so as to minimize the total cost of routing. The cost of the routing is ∑e fe(xe), where xe is the total flow on edge e and fe: ℝ+ → ℝ+ is a sub-additive cost function that models economies of scale for installing capacity on e. We obtain a polylogarithmic approximation for this problem. The algorithm is based on connections and insights from length-constrained network design. Along the way, we obtain a bicriteria approximation algorithm for a 2-vertex connected length-constrained problem, which is of independent interest.

We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph G = (V, E) and an integer connectivity requirement r(uv) for each u, v ∈ V. The objective is to find a minimum-weight subgraph H ⊆ G such that, for every pair of vertices u, v ∈ V, u and v are r(uv)-edge/vertex-connected. Recent work by [Ce Jin et al., 2024] obtained approximation algorithms for edge-connectivity augmentation, and via that, also derived algorithms for edge-connectivity SNDP (EC-SNDP). In this work we consider vertex-connectivity setting (VC-SNDP) and obtain several results for it as well as improved results for EC-SNDP. - We provide a general framework for solving connectivity problems including SNDP and others in streaming; this is based on a connection to fault-tolerant spanners. For VC-SNDP we provide an O(tk)-approximation in Õ(k^{1-1/t}n^{1 + 1/t}) space, where k is the maximum connectivity requirement, assuming an exact algorithm at the end of the stream. Using a refined LP-based analysis, we provide an O(β t)-approximation where β is the integrality gap of the natural cut-based LP relaxation. These are the first approximation algorithms in the streaming model for VC-SNDP. When applied to the EC-SNDP, our framework provides an O(t)-approximation in Õ(k^{1/2-1/(2t)}n^{1 + 1/t} + kn) space, improving the O(t log k)-approximation of [Ce Jin et al., 2024] using Õ(kn^{1+1/t}) space; this also extends to element-connectivity SNDP. - We consider vertex connectivity-augmentation in the link-arrival model. The input is a k-vertex-connected spanning subgraph G, and additional weighted links L arrive in the stream; the goal is to store the min-weight set of links such that G ∪ L is (k+1)-vertex-connected. We obtain constant-factor approximations in near-linear space for k = 1, 2. Our result for k = 2 is based on using the SPQR tree, a novel application for this well-known representation of 2-connected graphs.

We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is adirected edge-weighted graph G = (V,E ) and a collection of vertex pairs {(si,ti )}i∈[k]. The goal is to find a minimum cost subgraph H of G such that H contains an si -ti path for each i ∈ [k]. DSF is NP-Hard and is known to be hard to approximate to a factor of Ω(2log1-∈ (n )) for any fixed ∈ > 0 [17]. DSF admits approximation ratios of O (K1/2+∈) [10] and O (n2/3+∈) [4].

We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [CHKS09,KN11]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [CHKS09]. The rounding is based on recent results in hop-constrained oblivious routing [GHZ21], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [GL17,GML18,AJL20] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.

In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph G = (V,E), a root vertex r and a set S ⊆ V of k terminals. The goal is to find a min-cost subgraph that connects r to each of the terminals. DST admits an O(log² k/log log k)-approximation in quasi-polynomial time [Grandoni et al., 2022; Rohan Ghuge and Viswanath Nagarajan, 2022], and an O(k^{ε})-approximation for any fixed ε > 0 in polynomial-time [Alexander Zelikovsky, 1997; Moses Charikar et al., 1999]. Resolving the existence of a polynomial-time poly-logarithmic approximation is a major open problem in approximation algorithms. In a recent work, Friggstad and Mousavi [Zachary Friggstad and Ramin Mousavi, 2023] obtained a simple and elegant polynomial-time O(log k)-approximation for DST in planar digraphs via Thorup’s shortest path separator theorem [Thorup, 2004]. We build on their work and obtain several new results on DST and related problems. - We develop a tree embedding technique for rooted problems in planar digraphs via an interpretation of the recursion in [Zachary Friggstad and Ramin Mousavi, 2023]. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree [Naveen Garg et al., 2000], Covering Steiner Tree [Goran Konjevod et al., 2002] and the Polymatroid Steiner Tree [Gruia Călinescu and Alexander Zelikovsky, 2005] problems in planar digraphs. All these problems are hard to approximate to within a factor of Ω(log² n/log log n) even in trees [Eran Halperin and Robert Krauthgamer, 2003; Grandoni et al., 2022]. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² k) in planar digraphs. This is in contrast to general graphs where the integrality gap of this LP is known to be Ω(√k) [Leonid Zosin and Samir Khuller, 2002] and Ω(n^{δ}) for some fixed δ > 0 [Shi Li and Bundit Laekhanukit, 2022]. - We combine the preceding results with density based arguments to obtain poly-logarithmic approximations for the multi-rooted versions of the problems in planar digraphs. For DST our result improves the O(R + log k) approximation of [Zachary Friggstad and Ramin Mousavi, 2023] when R = ω(log² k).

Classical network design models, such as the Survivable Network Design problem (SNDP), are (partly) motivated by robustness to faults under the assumption that any subset of edges upto a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. Our primary interest is in the flexible graph connectivity model [Adjiashvili, 2013; Adjiashvili et al., 2020; Adjiashvili et al., 2022; Boyd et al., 2023], in which the edge set is partitioned into safe and unsafe edges. Given parameters p,q ≥ 1, the goal is to find a cheap subgraph that remains p-connected even after the failure of q unsafe edges. We also discuss the bulk-robust model [Adjiashvili et al., 2015; Adjiashvili, 2015] and the relative survivable network design model [Dinitz et al., 2022]. While SNDP admits a 2-approximation [K. Jain, 2001], the approximability of problems in these more complex models is much less understood even in special cases. We make two contributions. Our first set of results are in the flexible graph connectivity model. Motivated by a conjecture that a constant factor approximation is feasible when p and q are fixed, we consider two special cases. For the s-t case we obtain an approximation ratio that depends only on p,q whenever p+q > pq/2 which includes (p,2) and (2,q) for all p,q ≥ 1. For the global connectivity case we obtain an O(q) approximation for (2,q), and an O(p) approximation for (p,2) and (p,3) for any p ≥ 1, and for (p,4) when p is even. These are based on an augmentation framework and decomposing the families of cuts that need to be covered into a small number of uncrossable families. Our second result is a poly-logarithmic approximation for a generalization of the bulk-robust model when the "width" of the given instance (the maximum number of edges that can fail in any particular scenario) is fixed. Via this, we derive corresponding approximations for the flexible graph connectivity model and the relative survivable network design model. We utilize a recent framework due to Chen et al. [Chen et al., 2022] that was designed for handling group connectivity.

Multi-lingual question generation (QG) is the task of generating natural language questions for single answer passage in any given language. In this paper, we design a system for supporting multi-lingual QG in the "People Also Ask" (PAA) module for Bing. For zero shot setting, the primary challenge is to transfer the knowledge from trained QG model in the pivot language to other languages without further addition of training data in these languages. Compared to other zero-shot tasks, the differentiating and challenging aspect in QG is to preserve the question structure so that the resulting output is interrogative. Existing models for similar tasks tend to generate natural language queries or copy sub-span of the passage, failing to preserve the question structure. In our work, we demonstrate how knowledge transfer in multi-lingual IQG (Interrogative QG) can be significantly improved using auxiliary tasks either in multi-task or pre-training task setting. We explore two kinds of tasks - cross-lingual translation and multi-lingual denoising auto-encoding of questions, especially when using translate-train. Using data for 13 languages from Bing PAA as well as online A/B tests, we show that both of these tasks significantly improve the quality of zero-shot IQG on non-trained languages.

The systematic investigation of the vocal folds' physical phenomenon and corresponding kymographic vibratory patterns can establish clinically important relationships which are vital in the diagnosis of laryngeal disorders. The routine investigation is often done clinically through the in-vivo examination of human vocal folds using laryngoscopes. Physical modelling of human vocal folds overcomes the accessibility limitations of the laryngoscopes in imaging the medial and coronal parts of the vocal folds in-vivo, thus allowing investigation of mucosal wave propagation for different geometrical configurations of the vocal folds. Here, the modelled vocal folds are fabricated using flexible silicone compounds, which can closely reproduce the vibratory characteristics of human vocal folds. The kymogram, generated by recording the vibration pattern of the vocal folds, is useful in the analysis of its functional characteristics. The systematic investigation involves quantification of the vibratory parameters from the kymogram of the modelled vocal folds and establishing its relationship with the physical phenomenon. From the quantification, the important parameters: amplitude, open quotient, closed quotient, speed quotient and skewness are analysed. The quantified parameters reflect the influence of physical parameters on the vibratory characteristics of the vocal folds.