Search

In this paper, we first define the longest almost increasing subsequence with sliding windows (LaISW), a generalization that combines the longest increasing subsequence with sliding windows (LISW) problem and the longest almost increasing subsequence (LaIS) problem. For a numeric sequence A , a window size w and a tolerance constant c , the goal of the LaISW problem is to identify the LaIS within all windows of size w in A. In an almost increasing subsequence, slight decreases smaller than c are permitted. We propose an efficient algorithm for solving the LaISW problem. Instead of constructing the entire row tower, our algorithm computes the change in drop out (occurrence) for each element in the row tower. The time complexity of our algorithm is O (n L) , and the space complexity is O(L), where n and L represent the lengths of the input sequence and the LaISW answer, respectively. • Stock prices might exhibit an almost increasing (or decreasing) trend, but they are not strictly increasing. • We define longest almost increasing subsequence with sliding windows (LaISW). • Our algorithm calculates the changes in occurrences for each element in the row tower. • The time and space complexities of our algorithm are O (n L) and O(L), respectively. [ABSTRACT FROM AUTHOR]

Effectively balancing traffic in datacenter networks is a crucial operational goal. Most existing load balancing approaches are handcrafted to the structure of the network and/or network workloads. Thus, new load balancing strategies are required if the underlying network conditions change, e.g., due to hard or grey failures, network topology evolution, or workload shifts. While we can theoretically derive the optimal load balancing strategy by solving an optimization problem given certain traffic and topology conditions, these problems take too much time to solve and makes the derived solution stale to deploy. In this paper, we describe a load balancing scheme Learned Load Balancing (LLB), which is a general approach to finding an optimal load balancing strategy for a given network topology and workload, and is fast enough in practice to deploy the inferred strategies. LLB uses deep supervised learning techniques to learn how to handle different traffic patterns and topology changes, and adapts to any failures in the underlying network. LLB leverages emerging trends in network telemetry, programmable switching, and "smart" NICs. Our experiments show that LLB performs well under failures and can be expanded to more complex, multi-layered network topologies. We also prototype neural network inference on smartNICs to demonstrate the workability of LLB. [ABSTRACT FROM AUTHOR]

A new algorithm is proposed in this paper for computing the nearest polynomial to multiple given polynomials with a given zero in the real case, where the distance between polynomials is defined by the weighted ℓ 2 , q norm (0 < q ≤ 2). First, the problem is formulated as a univariate constrained non-convex minimization problem, where prior information of the coefficients of the polynomial can be embedded by selecting proper weights. Then, an iteratively reweighted algorithm is designed to solve the obtained problem, and also the convergence and rate of convergence are uniformly demonstrated for all q in (0 , 2 ]. Since all the existing methods for computing the nearest polynomial to multiple given polynomials with a given zero are limited to the real case, we ingeniously extend the results to the complex case. Finally, two representative examples that separately compute the nearest real and complex polynomials are presented to show the effectiveness of the proposed algorithm. • A weighted ℓ 2 , q -norm based minimization problem is constructed with prior information of polynomial embedded. • After converting the problem into a univariate problem, an iteratively reweighted algorithm is proposed to solve it. • Using properties of a concave function, convergence and rate of convergence of the proposed algorithm are provided. • It is the first time to study computation of the nearest polynomial to multiple given polynomials with a given zero in the complex case. [ABSTRACT FROM AUTHOR]

The hypercube is a very popular topology for the interconnection networks of parallel systems, and the folded hypercube is a variant of the hypercube. The folded hypercube attains much higher performance by introducing one additional link to each processing element. Therefore, there are many research activities regarding the folded hypercube. We focus on this topology and address an unresolved problem, that is, the set-to-set disjoint paths problem in it. In this paper, we show an algorithm that solves the problem in a folded hypercube in polynomial time. We prove the correctness of the algorithm. Moreover, we show that the time complexity of the algorithm is O (ν 3 log ⁡ ν) and the maximum length of the paths is 2 ν + 2 if the algorithm is applied to a ν -dimensional folded hypercube. • This study proposes an algorithm that solves the set-to-set disjoint paths problem in a folded hypercube in polynomial time. • (v + 1) paths are generated between two node sets, each of which has (v + 1) nodes, in a v -dimensional folded hypercube. • It is proved that the proposed algorithm solves the problem in a v -dimensional folded hypercube in O (v 3 log ⁡ v) time. • Also, it is proved that the lengths of the paths generated by the proposed algorithm are at most 2 v + 2. [ABSTRACT FROM AUTHOR]

In the multicast communication scenario, compared with broadcast encryption, broadcast signcryption or multi-receiver signcryption has additional ability to authenticate the source of the message. With the enhanced awareness of privacy preservation, ordinary users pay more attention to the identity leakage in the communication process. The primitive of anonymous broadcast signcryption has been proposed to solve this problem, which provides additional anonymity compared with the existing broadcast signcryption. However, most anonymous broadcast signcryption schemes only ensure the sender's identity concealment but ignore the anonymity of the receiver set. In this paper, we present a fully anonymous identity-based broadcast signcryption scheme, which meets insider unforgeability, outsider confidentiality, identity concealment of sender and full anonymity of the receiver set. In addition, our scheme has two further desirable characteristics. One is public verifiability which means any third party can verify the validity of the message source without knowing the private key provided by the receiver. The other is statelessness which means the user does not need to update the private key due to the join or revocation of other users. Moreover, our scheme has constant-size public parameters and private key as well as constant decryption complexity, which makes the scheme more suitable for deployment in devices with limited storage or low computing power such as IoT devices. [ABSTRACT FROM AUTHOR]

The fair k -median problem is one of the important clustering problems. The current best approximation ratio is 4.675 for this problem with 1-fairness violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. To our best knowledge, there is no available approximation algorithm for this problem without any fairness violation in doubling metrics. In this paper, we consider the fair k -median problem in doubling metrics and general metrics. We provide the first QPTAS for the fair k -median problem based on the hierarchical decomposition and dynamic programming process in doubling metrics. For applying a dynamic programming process to solve this problem, the distances from portals to facilities cannot be directly enumerated since each client may not be assigned to its closest open facility. To overcome the difficulties caused by the fairness constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get the cost between the portals of each block and the ones in its children. In order to satisfy the fairness constraints, we bound the fairness constraints of each open facility in the leaves of the split-tree based on the relation between the subproblem and the subproblems of its children. To obtain the assignment of the given instance and remove the fairness violation, we construct a new b -value min-cost max-flow model based on the set of open facilities. For the fair k -median problem in general metrics, we present a polynomial-time approximation algorithm with ratio O (log ⁡ k). Our approximation algorithm for the fair k -median problem in doubling metrics is the first result for the corresponding problem without any fairness violation in doubling metrics. [ABSTRACT FROM AUTHOR]

The Minimum Vertex Cover P roblem is the optimization problem of finding a vertex cover V c of minimal cardinality in a given graph. It is a classic NP-hard problem, and various algorithms have been suggested for it. In this paper, we start with a basic algorithm for solving the problem. Using a probabilistic idea, we use it to develop an improved algorithm. The algorithm is greedy; at each step it adds to the cover a vertex such that the expected cover size, if we continue randomly after this step, is minimal. We study the new algorithm theoretically and empirically, and run simulations to compare its performance to that of some algorithms of a similar nature. [ABSTRACT FROM AUTHOR]

Reconstructing input from a data structure entails determining whether an instance of the data structure is in fact valid or not, and if valid, discovering the underlying data that it represents. In this paper we consider the parameterized suffix array (pSA) along with its corresponding parameterized longest-common-prefix (pLCP) array and solve the following problem. Given two arrays of numbers as input, A and P , does there exist a parameterized string S such that A is its pSA and P is its pLCP array? If the answer is positive, our algorithm produces a string S whose pSA is A and whose pLCP array is P. Although the naive approach would have to consider an exponential number of possibilities for such a string S , our algorithm's time complexity is only O (n 2) for input arrays of size n. [ABSTRACT FROM AUTHOR]