Pruning 2-Connected Graphs

Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of?G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log?nlog?k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac{1}{\epsilon}\log^{2} n)$ approximation, while violating the budget by a factor of at most 2+ε.     

Approximation Algorithms for the Unsplittable Flow Problem

We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily over the graph. Our results are: We obtain an approximation ratio for UFP, where n is the number of vertices, is the maximum degree, and is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm gives an approximation. For certain strong constant-degree expanders considered by we obtain an approximation for the uniform capacity case. For UFP on the line and the ring, we give the first constant-factor approximation algorithms. All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either improve upon or are incomparable with previously known results for these problems. The main technique used for these results is randomized rounding followed by greedy alteration, and is inspired by the use of this idea in recent work.     

Content-adaptive wireless streaming of instructional videos

Video streaming over wireless networks is becoming increasingly important for a variety of applications. To accommodate the dynamic change of wireless network bandwidths, Quality of Service (QoS) scalable video streams need to be provided. This paper presents a system of content-adaptive streaming of instructional (lecture) videos over wireless networks for E-learning applications. We first provide a real-time content analysis method to detect and extract content regions from instructional videos, then apply a “leaking-video-buffer” model to adjust QoS of video streams dynamically based on video content. In content-adaptive video streaming, an adaptive feedback control scheme is also developed to transmit properly compressed video streams to video clients not only based on network bandwidth, but also based on video content and the preferences of users. Finally, we demonstrate the scalability and content adaptiveness of the proposed video streaming system with experimental results on several instructional videos.     

Content-adaptive wireless streaming of instructional videos

Video streaming over wireless networks is becoming increasingly important for a variety of applications. To accommodate the dynamic change of wireless network bandwidths, Quality of Service (QoS) scalable video streams need to be provided. This paper presents a system of content-adaptive streaming of instructional (lecture) videos over wireless networks for E-learning applications. We first provide a real-time content analysis method to detect and extract content regions from instructional videos, then apply a “leaking-video-buffer” model to adjust QoS of video streams dynamically based on video content. In content-adaptive video streaming, an adaptive feedback control scheme is also developed to transmit properly compressed video streams to video clients not only based on network bandwidth, but also based on video content and the preferences of users. Finally, we demonstrate the scalability and content adaptiveness of the proposed video streaming system with experimental results on several instructional videos.     

Engineered Cell-Membrane-Coated Nanoparticles Directly Present Tumor Antigens to Promote Anticancer Immunity

The recent success of immunotherapies has highlighted the power of leveraging the immune system in the fight against cancer. In order for most immune-based therapies to succeed, T cell subsets with the correct tumor-targeting specificities must be mobilized. When such specificities are lacking, providing the immune system with tumor antigen material for processing and presentation is a common strategy for stimulating antigen-specific T cell populations. While straightforward in principle, experience has shown that manipulation of the antigen presentation process can be incredibly complex, necessitating sophisticated strategies that are difficult to translate. Herein, the design of a biomimetic nanoparticle platform is reported that can be used to directly stimulate T cells without the need for professional antigen-presenting cells. The nanoparticles are fabricated using a cell membrane coating derived from cancer cells engineered to express a co-stimulatory marker. Combined with the peptide epitopes naturally presented on the membrane surface, the final formulation contains the necessary signals to promote tumor antigen-specific immune responses, priming T cells that can be used to control tumor growth. The reported approach represents an emerging strategy that can be used to develop multiantigenic, personalized cancer immunotherapies.     

A Note on Multiflows and Treewidth

We consider multicommodity flow problems in capacitated graphs where the treewidth of the underlying graph is bounded by r. The parameter r is allowed to be a function of the input size. An instance of the problem consists of a capacitated graph and a collection of terminal pairs. Each terminal pair has a non-negative demand that is to be routed between the nodes in the pair. A class of optimization problems is obtained when the goal is to route a maximum number of the pairs in the graph subject to the capacity constraints on the edges. Depending on whether routings are fractional, integral or unsplittable, three different versions are obtained; these are commonly referred to respectively as maximum MCF, EDP (the demands are further constrained to be one) and UFP. We obtain the following results in such graphs.

On average throughput and alphabet size in network coding

We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. We relate these benefits to the integrality gap of a standard linear programming formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with N receivers where network coding offers benefits proportional to /spl radic/N. We also discuss other throughput measures in networks, and show how in certain classes of networks, average throughput bounds can be translated into minimum throughput bounds, by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.     

Routing bandwidth guaranteed paths with local restoration in label switched networks

The emerging multiprotocol label switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites. This basic label switched path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along primary path fail. We address the problem of distributed routing of restoration paths, which can be defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP, and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used. We introduce the concept of "backtracking" to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance D: 1) no backtracking (D=0); 2) limited backtracking (D=k); and 3) unlimited backtracking (D=/spl infin/). We use a link cost model that captures bandwidth sharing among links using various types of aggregate link-state information. We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.     

Extracting content from instructional videos by statistical modelling and classification

This paper presents a robust approach to extracting content from instructional videos for handwritten recognition, indexing and retrieval, and other e-learning applications. For the instructional videos of chalkboard presentations, retrieving the handwritten content (e.g., characters, drawings, figures) on boards is the first and prerequisite step towards further exploration of instructional video content. However, content extraction in instructional videos is still challenging due to video noise, non-uniformity of the color in board regions, light condition changes in a video session, camera movements, and unavoidable occlusions by instructors. To solve this problem, we first segment video frames into multiple regions and estimate the parameters of the board regions based on statistical analysis of the pixels in dominant regions. Then we accurately separate the board regions from irrelevant regions using a probabilistic classifier. Finally, we combine top-hat morphological processing with a gradient-based adaptive thresholding technique to retrieve content pixels from the board regions. Evaluation of the content extraction results on four full-length instructional videos shows the high performance of the proposed method. The extraction of content text facilitates the research on full exploitation of instructional videos, such as content enhancement, indexing, and retrieval.