In this paper, we consider a distributed stochastic nonconvex optimization problem for multiagent systems. We propose a distributed stochastic gradient-tracking method with event-triggered communication. A group of agents cooperatively finds a critical point of the sum of local cost functions, which are smooth but not necessarily convex. We show that the proposed algorithm achieves a sublinear convergence rate by appropriately tuning the step size and the trigger threshold. Moreover, we show that agents can effectively solve a nonconvex optimization problem by the proposed event-triggered algorithm with less communication than by the existing time-triggered gradient-tracking algorithm. We confirm the validity of the proposed method by numerical experiments.

In this paper we study a recently proposed variant of the r-gathering problem. An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r or more customers are assigned to each open facility. (Each facility needs enough number of customers to open.) Given an opening cost op(f) for each f∈F, and a connecting cost co(c,f) for each pair of c∈C and f∈F, the cost of an r-gathering A is max{maxc∈C{co(c, A(c))}, maxf∈F'{op(f)}}. The r-gathering problem consists of finding an r-gathering having the minimum cost. Assume that F is a set of locations for emergency shelters, op(f) is the time needed to prepare a shelter f∈F, and co(c,f) is the time needed for a person c∈C to reach assigned shelter f=A(c)∈F. Then an r-gathering corresponds to an evacuation plan such that each open shelter serves r or more people, and the r-gathering problem consists of finding an evacuation plan minimizing the evacuation time span. However in a solution above some person may be assigned to a farther open shelter although it has a closer open shelter. It may be difficult for the person to accept such an assignment for an emergency situation. Therefore, Armon considered the problem with one more additional constraint, that is, each customer should be assigned to a closest open facility, and gave a 9-approximation polynomial-time algorithm for the problem. We have designed a simple 3-approximation algorithm for the problem. The running time is O(r|C||F|).

In Variant 4 of the one-way trading game [El-Yaniv, Fiat, Karp, and Turpin, 2001], a player has one dollar at the beginning and wants to convert it to yen only by one-way conversion. The exchange rate is guaranteed to fluctuate between m and M, and only the maximum fluctuation ratio φ = M/m is informed to the player in advance. The performance of an algorithm for this game is measured by the competitive ratio. El-Yaniv et al. derived the best possible competitive ratio over all algorithms for this game. However, it seems that the behavior of the best possible algorithm itself has not been explicitly described. In this paper we reveal the behavior of the best possible algorithm by solving a linear optimization problem. The behavior turns out to be quite different from that of the best possible algorithm for Variant 2 in which the player knows m and M in advance.

In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

Aiming at the problem of “energy hole” caused by random distribution of nodes in large-scale wireless sensor networks (WSNs), this paper proposes an adaptive energy-efficient balanced uneven clustering routing protocol (AEBUC) for WSNs. The competition radius is adaptively adjusted based on the node density and the distance from candidate cluster head (CH) to base station (BS) to achieve scale-controlled adaptive optimal clustering; in candidate CHs, the energy relative density and candidate CH relative density are comprehensively considered to achieve dynamic CH selection. In the inter-cluster communication, based on the principle of energy balance, the relay communication cost function is established and combined with the minimum spanning tree method to realize the optimized inter-cluster multi-hop routing, forming an efficient communication routing tree. The experimental results show that the protocol effectively saves network energy, significantly extends network lifetime, and better solves the “energy hole” problem.

The Volterra filter is one of the digital filters that can describe nonlinearity. In this paper, we analyze the dynamic behaviors of an adaptive signal processing system with the Volterra filter for nonwhite input signals by a statistical-mechanical method. Assuming the self-averaging property with an infinitely long tapped-delay line, we derive simultaneous differential equations that describe the behaviors of macroscopic variables in a deterministic and closed form. We analytically solve the derived equations to reveal the effect of the nonwhiteness of the input signal on the adaptation process. The results for the second-order Volterra filter show that the nonwhiteness decreases the mean-square error (MSE) in the early stages of the adaptation process and increases the MSE in the later stages.

Annealing computation has recently attracted attention as it can efficiently solve combinatorial optimization problems using an Ising spin-glass model. Stochastic cellular automata annealing (SCA) is a promising algorithm that can realize fast spin-update by utilizing its parallel computing capability. However, in SCA, pinning effect control to suppress the spin-flip probability is essential, making escaping from local minima more difficult than serial spin-update algorithms, depending on the problem. This paper proposes a novel approach called APC-SCA (Autonomous Pinning effect Control SCA), where the pinning effect can be controlled autonomously by focusing on individual spin-flip. The evaluation results using max-cut, N-queen, and traveling salesman problems demonstrate that APC-SCA can obtain better solutions than the original SCA that uses pinning effect control pre-optimized by a grid search. Especially in solving traveling salesman problems, we confirm that the tour distance obtained by APC-SCA is up to 56.3% closer to the best-known compared to the conventional approach.

Binary Neural Networks (BNN) have binarized neuron and connection values so that their accelerators can be realized by extremely efficient hardware. However, there is a significant accuracy gap between BNNs and networks with wider bit-width. Conventional BNNs binarize feature maps by static globally-unified thresholds, which makes the produced bipolar image lose local details. This paper proposes a multi-input activation function to enable adaptive thresholding for binarizing feature maps: (a) At the algorithm level, instead of operating each input pixel independently, adaptive thresholding dynamically changes the threshold according to surrounding pixels of the target pixel. When optimizing weights, adaptive thresholding is equivalent to an accompanied depth-wise convolution between normal convolution and binarization. Accompanied weights in the depth-wise filters are ternarized and optimized end-to-end. (b) At the hardware level, adaptive thresholding is realized through a multi-input activation function, which is compatible with common accelerator architectures. Compact activation hardware with only one extra accumulator is devised. By equipping the proposed method on FPGA, 4.1% accuracy improvement is achieved on the original BNN with only 1.1% extra LUT resource. Compared with State-of-the-art methods, the proposed idea further increases network accuracy by 0.8% on the Cifar-10 dataset and 0.4% on the ImageNet dataset.

In this paper, a wireless communication network that uses unmanned aerial vehicles (UAVs) in the sky to transmit information between ground users is considered. We highlight a delay-tolerant network, where information is relayed in a store-and-forward fashion by establishing two types of intermittent communication links: between a UAV and a user (UAV-to-user) and between UAVs (UAV-to-UAV). Thus, a flight algorithm that controls the movement of the UAVs is crucial in achieving rapid information transmission. Our study proposes new flight algorithms that simultaneously consider the two types of communication links. In UAV-to-UAV links, the direct information transmission between two UAVs and the indirect transmission through other UAVs are considered separately. The movement of the UAVs is controlled by solving an optimization problem at certain time intervals, with a variable consideration ratio of the two types of links. In addition, we investigate not only the case where all UAVs move cooperatively but also the case where each UAV moves autonomously. Simulation results show that the proposed algorithms are effective. Moreover, they indicate the existence of an optimal consideration ratio of the two types of communication and demonstrate that our approach enables the control of frequencies of establishing the communication links. We conclude that increasing the frequency of indirect communication between UAVs improves network performance.

Non-Terrestrial-Network (NTN) can provide seamless and ubiquitous connectivity of massive devices. Thus, the feeder links between satellites and gateways need to provide essentially high data transmission rates. In this paper, we focus on a typical high-capacity scenario, i.e., LEO-IoT, to find an optimal satellite selection schema to maximize the capacity of feeder links. The proposed schema is able to obtain the optimal mapping among all the satellites and gateways. By comparing with maximum service time algorithm, the proposed schema can construct a more balanced and reasonable connection pattern to improve the efficiency of the gateways. Such an advantage will become more significant as the number of satellites increases.

This paper formulates a class-E synchronous RF rectifier from a new viewpoint. The key point is to introduce a matrix and convolute the DC terms into RF matrices. The explicit expression of input impedance is demonstrated in plane geometry. We find out their input impedance exhibits a geodesic arc in hyperbolic geometry under ZVS operation, where the theoretical RF-DC conversion efficiency results in 100%. We verify the developed theory both numerically (circuit simulation) and experimentally (6.78MHz, 100W). We confirm that the input impedance becomes a geodesic arc for a wide range of DC load resistance. The presented theory is quite elegant since it is based on a matrix-based formulation and plane-geometrical expression.

The maximal independent set (MIS) problem is one of the most fundamental problems in the field of distributed computing. This paper focuses on the MIS problem with unreliable communication between processes in the system. We propose a relaxed notion of MIS, named almost MIS (ALMIS), and show that the loosely-stabilizing algorithm proposed in our previous work can achieve exponentially long holding time with logarithmic convergence time and space complexity regarding ALMIS, which cannot be achieved at the same time regarding MIS in our previous work.

The Variational Quantum Eigensolver (VQE) algorithm is gaining interest for its potential use in near-term quantum devices. In the VQE algorithm, parameterized quantum circuits (PQCs) are employed to prepare quantum states, which are then utilized to compute the expectation value of a given Hamiltonian. Designing efficient PQCs is crucial for improving convergence speed. In this study, we introduce problem-specific PQCs tailored for optimization problems by dynamically generating PQCs that incorporate problem constraints. This approach reduces a search space by focusing on unitary transformations that benefit the VQE algorithm, and accelerate convergence. Our experimental results demonstrate that the convergence speed of our proposed PQCs outperforms state-of-the-art PQCs, highlighting the potential of problem-specific PQCs in optimization problems.

An interconnection network is an inevitable component for constructing parallel computers. It connects computation nodes so that the nodes can communicate with each other. As a parallel computation essentially requires inter-node communication according to a parallel algorithm, the interconnection network plays an important role in terms of communication performance. This paper focuses on the collective communication that is frequently performed in parallel computation and this paper addresses the Cup-Stacking method that is proposed in our preceding work. The key issues of the method are splitting a large packet into slices, re-shaping the slice, and stacking the slices, in a genetic algorithm (GA) manner. This paper discusses extending the Cup-Stacking method by introducing additional items (genes) and proposes the extended Cup-Stacking method. Furthermore, this paper places comprehensive discussions on the drawbacks and further optimization of the method. Evaluation results reveal the effectiveness of the extended method, where the proposed method achieves at most seven percent improvement in duration time over the former Cup-Stacking method.

To cope with ever growing mobile data traffic, we recently proposed a concept of cellular ultra-dense radio access network (RAN). In the cellular ultra-dense RAN, a number of distributed antennas are deployed in the base station (BS) coverage area (cell) and user-clusters are formed to perform small-scale distributed multiuser multi-input multi-output (MU-MIMO) transmission and reception in each user-cluster in parallel using the same frequency resource. We also proposed a decentralized interference coordination (IC) framework to effectively mitigate both intra-cell and inter-cell interferences caused in the cellular ultra-dense RAN. The inter-cell IC adopted in this framework is the fractional frequency reuse (FFR), realized by applying the channel segregation (CS) algorithm, and is called CS-FFR in this paper. CS-FFR divides the available bandwidth into several sub-bands and allocates multiple sub-bands to different cells. In this paper, focusing on the optimization of the CS-FFR, we find by computer simulation the optimum bandwidth division number and the sub-band allocation ratio to maximize the link capacity. We also discuss the convergence speed of CS-FFR in a cellular ultra-dense RAN.

We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2|ε(S)|)-time, where ε(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surroundingpolygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon.

In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1) × (n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n × 2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 20n × 16n grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 10n × 5n grid if T(G) has exactly five leaves. We also present a linear-time algorithm to find such a drawing.

The bin packing problem is a problem of finding an assignment of a sequence of items to a minimum number of bins, each of capacity one. An online algorithm for the bin packing problem is an algorithm that irrevocably assigns each item one by one from the head of the sequence. Gutin, Jensen, and Yeo (2006) considered a version in which all items are only of two different sizes and the online algorithm knows the two possible sizes in advance, and gave an optimal online algorithm for the case when the larger size exceeds 1/2. In this paper we provide an optimal online algorithm for some of the cases when the larger size is at most 1/2, on the basis of a framework that facilitates the design and analysis of algorithms.

For any m strings of total length n, we propose an O(mn log n)-time, O(n)-space algorithm that finds a maximal common subsequence of all the strings, in the sense that inserting any character in it no longer yields a common subsequence of them. Such a common subsequence could be treated as indicating a nontrivial common structure we could find in the strings since it is NP-hard to find any longest common subsequence of the strings.

Physical Unclonable Function (PUF) is a promising lightweight hardware security primitive that can extract device fingerprints for encryption or authentication. However, extracting fingerprints from either the chip or the board individually has security flaws and cannot provide hardware system-level security. This paper proposes a new Chip-PCB hybrid PUF(CPR PUF) in which Weak PUF on PCB is combined with Strong PUF inside the chip to generate massive responses under the control of challenges of on-chip Strong PUF. This structure tightly couples the chip and PCB into an inseparable and unclonable unit thus can verify the authenticity of chip as well as the board. To improve the uniformity and reliability of Chip-PCB hybrid PUF, we propose a lightweight key generator based on a reliability self-test and debiasing algorithm to extract massive stable and secure keys from unreliable and biased PUF responses, which eliminates expensive error correction processes. The FPGA-based test results show that the PUF responses after robust extraction and debiasing achieve high uniqueness, reliability, uniformity and anti-counterfeiting features. Moreover, the key generator greatly reduces the execution cost and the bit error rate of the keys is less than 10-9, the overall security of the key is also improved by eliminating the entropy leakage of helper data.