Theoretical Computer Science

In this paper, we study the semi-online machine covering problem on two hierarchical machines, whose objective is to maximize the minimum machine load. When the processing times are discrete by \(\{1,2,2^{2},\ldots ,2^{k}\}\) with \(k\ge 2\), we prove that no algorithm can have a competitive ratio less than \(2^{k}\) and present an optimal semi-online algorithm with competitive ratio \(2^{k}\).

We study the problem of learning Gaussian Mixture Model (GMM) in one dimension. Given samples access to a mixture f of k Gaussians and an accurate parameter \(\epsilon >0\), our algorithm takes \(\tilde{O}{(\frac{k}{\epsilon ^5})}\) samples, runs in polynomial time and outputs a mixture g of at most \(\tilde{O}(\min \{\frac{k^2}{\epsilon ^2},\frac{k}{\epsilon ^3}\})\) Gaussians such that the total variation distance between f and g is at most \(\epsilon \). This improves the previous result by [4], which uses \(O(\frac{k^2}{\epsilon ^6})\) samples and outputs a mixture of \(O(\frac{k}{\epsilon ^3})\) Gaussians. Our algorithm uses LP rounding technique to find the sparse solution of a linear programming. The main technical contribution of us is a non-trivial inequality for Gaussians, which may be interesting in its own right.

We also consider the problem of properly learning mixture of two Gaussians. We show how to reduce the learning task to the closest pair problem in \(L_{\infty }\)-norm. Our algorithm takes \(\tilde{O}(\frac{1}{\epsilon ^2})\) samples and runs in time \(\tilde{O}(\frac{1}{\epsilon ^{4.001}})\). Our result improves the previous result by [7], which uses \(\tilde{O}(\frac{1}{\epsilon ^2})\) samples and runs in time \(\tilde{O}(\frac{1}{\epsilon ^5})\).

Retina images contain a lot of useful information for medical judgment, blood vessel extrusion, the ratio of the arteriovenous width and whether there is lesion area are vital to disease judgment, it is difficult to draft a unified standard for artificial judgment due to subjectivity. Traditional approaches to obtain the three indicators mentioned above include image processing and machine learning, these approaches have relatively poor accuracy or too many restrictions. In order to solve these problems, we propose a customized fully convolutional network, RI-FCN, based on image semantic segmentation for retina image detection. In our proposed method, there are five convolution layers, three down-pooling layers and two up-pooling layers. This structure can classify every pixel into predefined categories and show in different colors and small features can also be presented which is vital in the detection of blood vessel extrusion. Using the RI-FCN model, identification accuracy rate of arteriovenous width ratio, extrusion and lesion area can be increased to 92.23%, 90.99% and 98.13% respectively.

RFID three-party authentication protocol based on NTRU cryptosystem is a type of multi-entities authentication protocol. Unlike other RFID mutual authentication protocols, this protocol realizes mutual authentication of Server to Reader, and Server to Tag. Model checking is a formal method to check the correctness specifications hold in each state on concurrent and distributed systems, which can be used to verify the security of network protocol. A multi-channels constructing method is proposed to build this protocol model for formal analysis, then authentication property of the protocol is verified by model checker SPIN. Formal verification result reveals that an attack exists in this protocol, hence the protocol cannot guarantee the security of the three-party authentication protocol. The modeling method proposed above has great significance on security analysis for such three-party authentication protocols.

The Near Filed Communication (NFC) is widely used on mobile devices and make it possible to take advantage of NFC system to complete mobile payment. But with the development of NFC, its problem are increasingly exposed, especially the security and privacy of authentication. Logic of events is a formal method to describe the protocol state transition and algorithm in concurrent and distributed systems, which can be used to prove the security of network protocols. Based on logic of events, we propose migration rule and derive inheritability to reduce redundancy and complexity of protocol analysis procedure, and improve efficiency of protocol analysis. We study the KerNeeS protocol which providing mutual authentication between POS and NFC phone, and conclude that the protocol can guarantee authentication between entities involved in the payment for secure payment transactions. The logic of events can be applied to the formal analysis of similar mobile payment protocols.

Selfish bin packing considers a cost-sharing system of the classical bin packing problem, where each item is controlled by a selfish agent and aims to minimize the sharing cost. In this paper we study an incentive mechanism: Interest-Matrix-based (IM-based) mechanism, a new perspective that focuses on the interest or the satisfaction between any pair of items rather than personal sharing cost. Under the IM-based mechanism, we show that \(PoA\le 1.7\) for general instances with item size inside \((1/n_{0},1]\), where \(n_{0}\) is an arbitrary large integer. In special, when \(n_{0}=4\), the PoA of the IM-based mechanism does not exceed 1.5.

A subset \(S \subseteq V(G)\) in a graph \(G=(V,E)\) is a connected [j, k]-set, if it satisfies that G[S] is a connected subgraph of G and every vertex \(v \in V \setminus S\), \(j \le |N(v) \cap S| \le k\) for non-negative integers \(j<k\). In this paper, we study the connected [1, 2]-domination number of graph G, which denoted \(\gamma _{c[1,2]}(G)\). We discussed the graphs with \(\gamma _{c[1,2]}(G)=n\) and the graphs with \(\gamma _{c[1,2]}(G)=\gamma _c(G)\). In the end, the CONNECTED [1, 2]-SET Problem has been proved to be NP-complete for bipartite graphs.

Hyperspectral remote sensing image data has been widely used in a variety of applications due to its continuous spectrum and high spectral resolution. However, reducing huge dimensions with high data relevance is time-consuming, and parallel processing is required to accelerate this process. In the previous work, the KPCA (Kernel Principal Component Analysis), a nonlinear dimensionality reduction method was studied, and a parallel KPCA algorithm was proposed based on heterogeneous system with a single GPU, and achieved the desired experimental results. However, as data scale grows, the proposed solution would consume all the available memory on a single node and encounter performance bottleneck. Therefore, to tackle the limitation of insufficient memory caused by the reduction of large-scale hyperspectral data dimension, in this paper the intra-node parallelization using multi-core CPUs and many-core GPUs are exploited to improve the parallel hierarchy of distributed-storage KPCA. Finally, we designed and implemented a multilevel hybrid parallel KPCA algorithm that achieves 2.75–9.27 times speedup compared to the traditional coarse-grained parallel KPCA method on MPI.

In this paper, we study a problem of the two-machine flow shop scheduling problem with intermediate transportation. This problem has been studied in [2, 4, 17]. The best approximation algorithm was presented in [17] with a two approximation ratio to our best knowledge. We propose a \((\frac{5}{3}+\varepsilon )\)-approximation algorithm for this problem, where \(\varepsilon >0\). Moreover, our algorithm can reach the lower bound \(\frac{5}{3}\) asymptotically given by [2] when \(\varepsilon \) is close to 0.

Interactive segmentation has been successfully applied to various applications such as image editing, computer vision, image identification. Most of existing methods require interaction for each single image segmentation, which costs too much labor interactions. To address this issue, we propose a kernel based semi-supervised learning framework with manifold regularization for interactive image segmentation in this paper. Specifically, by manifold regularization, our algorithm makes similar superpixel pair bearing the same label. Moreover, the learned classifier on one single image is directly used to similar images for segmentation. Extensive experimental results demonstrate the effectiveness of the proposed approach.

Chronic wounds have a long recovery time, occur extensively, and are difficult to treat. They cause not only great suffering to many patients but also bring enormous work burden to hospitals and doctors. Therefore, an automated chronic wound detection method can efficiently assist doctors in diagnosis, or help patients with initial diagnosis, reduce the workload of doctors and the treatment costs of patients. In recent years, due to the rise of big data, machine learning methods have been applied to Image Identification, and the accuracy of the result has surpassed that of traditional methods. With the fully convolutional neural network proposed, image segmentation and target detection have also achieved excellent results. However, due to the protection of patient privacy, medical images are often difficult to obtain and insufficient training data leads to poor segmentation and recognition. To solve the above problem, we propose the chronic wounds image generator based on DCGANs. First, we select high-quality images of chronic wounds and process them to form a data set containing 520 images. Then we build a generator and discriminator network model to generate new images. Finally, we use the existing methods of chronic wound segmentation and recognition to test. The results show that the generated images can be used to expand the training set and further improve the segmentation and recognition accuracy.