In Mobile Edge Computing (MEC), each edge server can be configured with only a small number of functions due to the limited capacity various resources. Meanwhile, mobile applications become more complicated, consisting multiple dependent tasks which are typically modeled as Directed Acyclic Graph (DAG). computing, when an application arrives, we need place and schedule its onto servers and/or remote cloud, where execute configured. this work, jointly consider problem task placement...

In edge-cloud computing, a set of servers (called edge servers) are deployed near the mobile devices to allow these offload their jobs and subsequently obtain results from with low latency. One fundamental problem in systems is how dispatch schedule so that job response time (defined as interval between release arrival computation result at device) minimized. this paper, we propose general model for problem, where generated arbitrary order times then offloaded both upload download delays....

A coflow is a collection of related parallel flows that occur typically between two stages multi-stage compute task in network, such as shuffle MapReduce. The abstraction allows applications to convey their semantics the network so application-level requirements (e.g., minimizing completion time slowest flow) can be better satisfied. In this paper, we study routing and scheduling multiple coflows minimize average (CCT). We first propose rounding-based randomized approximation algorithm,...

We study the problem of constructing ε-coresets for (k, z)-clustering in a doubling metric M(X, d). An ε-coreset is weighted subset S ⊆ X with weight function w : → ℝ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">≥0</sub> , such that any k-subset C ∈ [X] <sup xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> it holds Σ xmlns:xlink="http://www.w3.org/1999/xlink">x∈S</sub> w(x) · d xmlns:xlink="http://www.w3.org/1999/xlink">z</sup> (x, C) (1 ±...

We devise $\epsilon$-coresets for robust $(k,z)$-Clustering with $m$ outliers through black-box reductions to vanilla case. Given an $\epsilon$-coreset construction clustering size $N$, we construct coresets of $N\cdot \mathrm{poly}\log(km\epsilon^{-1}) + O_z\left(\min\{km\epsilon^{-1}, m\epsilon^{-2z}\log^z(km\epsilon^{-1}) \}\right)$ various metric spaces, where $O_z$ hides $2^{O(z\log z)}$ factors. This increases the coreset by a small multiplicative factor...

A coflow is a collection of related parallel flows that occur typically between two stages multi-stage computing task in network, such as shuffle MapReduce. The abstraction allows applications to convey their semantics the network so application-level requirements can be better satisfied. In this paper, we study routing and scheduling multiple coflows minimize total weighted completion time (CCT). We first propose rounding-based randomized approximation algorithm, called OneCoflow, for...

In a recent work, [19] studied the following "fair" variants of classical clustering problems such as $k$-means and $k$-median: given set $n$ data points in $\mathbb{R}^d$ binary type associated to each point, goal is cluster while ensuring that proportion roughly same its underlying proportion. Subsequent work has focused on either extending this setting when point multiple, non-disjoint sensitive types race gender [6], or address problem algorithms above do not scale well. The main...

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees sensitivity to job latency. Therefore, multitude utility functions the response time need be considered by underlying dispatching and scheduling mechanism. Nonetheless, previous works in edge mainly focused on either one kind function (e.g., linear, sigmoid, or hard deadline) different kinds utilities separately. In this paper, we investigate online strategies under setting coexistence...

In Mobile Edge Computing, edge servers have limited storage and computing resources that can only support a small number of functions. Meanwhile, mobile applications are becoming more complex, consisting multiple dependent tasks, modeled as Directed Acyclic Graph (DAG). When request arrives, typically in an online manner with deadline specified, we need to configure the assign tasks for efficient processing. This work jointly considers problem task placement scheduling on-demand function...

Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a request might be relayed to other caches or bypassed directly the memory when cache miss happens. We take relaying, bypassing fetching costs altogether into consideration. first show inherent difficulty of problem even requests are uniform cost. propose an O(log K)-competitive randomized algorithm Camul O(K)-competitive...

We consider the general (J, K)-secretary problem, where n totally ordered items arrive in a random order. An algorithm observes relative merits of arriving and is allowed to make J selections. The objective maximize expected number selected among K best items.Buchbinder, Jain Singh proposed finite linear program (LP) that completely characterizes but it difficult analyze asymptotic behavior its optimal solution as tends infinity. Instead, we prove formal connection between model an infinite...

Torus networks are widely used in supercomputing. However, due to their complex topology and large number of nodes, it is difficult for analysts perceive the messages flow these networks. We propose a visualization framework called TorusVisND that uses modern information techniques allow see network its communication patterns single display control amount shown via filtering temporal domains. For this purpose we provide three cooperating visual interfaces. The main interface display. It two...

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of given collection subsets (regions or neighborhoods) underlying metric space.We give randomized polynomial time approximation scheme (PTAS) when regions are fat weakly disjoint. This notion was first defined QPTAS for problem [SODA 2010: Chan and Elbassioni]. combine techniques previous work, together recent PTAS TSP [STOC 2012: Bartal, Gottlieb...

We consider a generalization of the Steiner tree problem, forest problem , in Euclidean plane: input is multiset \(X\subseteq{\mathbb{R}}^{2}\) partitioned into \(k\) color classes \(C_{1},\ldots,C_{k}\subseteq X\) . The goal to find minimum-cost graph \(G\) such that every class \(C_{i}\) connected study this streaming setting, where stream consists insertions and deletions points \(X\) Each point \(x\in arrives with its \(\mathsf{color}(x)\in[k]\) as usual for dynamic geometric streams,...

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find shortest tour that visits each of a given collection subsets (regions or neighborhoods) underlying metric space. give randomized polynomial-time approximation scheme (PTAS) when regions are fat weakly disjoint. This notion was first defined QPTAS for problem SODA 2010 (Chan and Elbassioni 2010). partitioned into constant number groups, where group, should have common upper bound on...

We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by in rounds, and algorithm maintains feasible that is independent underlying matroid. In each round when new element arrives, may accept into its possibly remove elements it, provided resulting still independent. The goal to maximize value of final monotone function, which has oracle access.For k-uniform matroids, we give deterministic competitive ratio...

Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a request might be relayed to other caches or bypassed directly the memory when cache miss happens. We can also choose fetch files from conduct replacement if necessary. take relaying, bypassing fetching costs altogether into consideration. first show inherent difficulty of problem even requests are uniform costs. propose...

In latency-sensitive file caching systems such as Content Delivery Networks (CDNs) and Mobile Edge Computing (MEC), the latency of fetching a missing to local cache can be significant. Recent studies have revealed that successive requests same before completes could still suffer (so-called delayed hits).Motivated by practical scenarios, we study online general problem with hits bypassing, i.e., request may bypassed processed directly at remote data center. The objective is minimize total...

In Euclidean Uniform Facility Location, the input is a set of clients in $\mathrm{R}^{d}$ and goal to place facilities serve them, so as minimize total cost opening plus connecting clients. We study classical setting dynamic geometric streams, where are presented sequence insertions deletions points grid $\{1,ldots\,\Delta \}^{d}$, we focus on high-dimensional regime, algorithm's space complexity must be polynomial (and certainly not exponential) $d \cdot \log \Delta$.We present new...

We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by in rounds, and algorithm maintains feasible that is independent underlying matroid. In each round when new element arrives, may accept into its possibly remove elements it, provided resulting still independent. The goal to maximize value of final monotone function, which has oracle access. For k -uniform matroids, we give deterministic competitive...

Previous chapter Next Full AccessProceedings Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts Online K-Item Auction and Bipartite K-Matching with Random Arrival OrderT-H. Hubert Chan, Fei Chen, Shaofeng H.-C. JiangT-H. Jiangpp.1169 - 1188Chapter DOI:https://doi.org/10.1137/1.9781611973730.78PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail...