Hiroshi FUJIWARA Yuta WANIKAWA Hiroaki YAMAMOTO
The performance of online algorithms for the bin packing problem is usually measured by the asymptotic approximation ratio. However, even if an online algorithm is explicitly described, it is in general difficult to obtain the exact value of the asymptotic approximation ratio. In this paper we show a theorem that gives the exact value of the asymptotic approximation ratio in a closed form when the item sizes and the online algorithm satisfy some conditions. Moreover, we demonstrate that our theorem serves as a powerful tool for the design of online algorithms combined with mathematical optimization.
Carlos MANSO Pol ALEMANY Ricard VILALTA Raul MUÑOZ Ramon CASELLAS Ricardo MARTÍNEZ
The need of telecommunications operators to reduce Capital and Operational Expenditures in networks which traffic is continuously growing has made them search for new alternatives to simplify and automate their procedures. Because of the different transport network segments and multiple layers, the deployment of end-to-end services is a complex task. Also, because of the multiple vendor existence, the control plane has not been fully homogenized, making end-to-end connectivity services a manual and slow process, and the allocation of computing resources across the entire network a difficult task. The new massive capacity requested by Data Centers and the new 5G connectivity services will urge for a better solution to orchestrate the transport network and the distributed computing resources. This article presents and demonstrates a Network Slicing solution together with an end-to-end service orchestration for transport networks. The Network Slicing solution permits the co-existence of virtual networks (one per service) over the same physical network to ensure the specific service requirements. The network orchestrator allows automated end-to-end services across multi-layer multi-domain network segments making use of the standard Transport API (TAPI) data model for both l0 and l2 layers. Both solutions will allow to keep up with beyond 5G services and the higher and faster demand of network and computing resources.
Kento KIMURA Kazuyuki AMANO Tetsuya ARAKI
Given a box of some specified size and a number of pieces of some specified shape, the anti-slide problem considers how to pack the pieces such that none of the pieces in the box can slide in any direction. The object is to find such a sparsest packing. In this paper, we consider the problem for the case of a two-dimensional square box using T-tetromino pieces. We show that, for a square box of side length n, the number of pieces in a sparsest packing is exactly $lfloor 2n/3 floor$ when n≢0 (mod 3), and is between 2n/3-1 and n-1 when n≡0 (mod 3).
Hiroshi HAGA Takuya ASAI Shin TAKEUCHI Harue SASAKI Hirotsugu YAMAMOTO Koji SHIGEMURA
We developed an 8.4-inch electrostatic-tactile touch display using a segmented-electrode array (30×20) as both tactile pixels and touch sensors. Each pixel can be excited independently so that the electrostatic-tactile touch display allows presenting real localized tactile textures in any shape. A driving scheme in which the tactile strength is independent of the grounding state of the human body by employing two-phased actuation was also proposed and demonstrated. Furthermore, tactile crosstalk was investigated to find it was due to the voltage fluctuation in the human body and it was diminished by applying the aforementioned driving scheme.
Tomohiro KORIKAWA Akio KAWABATA Fujun HE Eiji OKI
The performance of packet processing applications is dependent on the memory access speed of network systems. Table lookup requires fast memory access and is one of the most common processes in various packet processing applications, which can be a dominant performance bottleneck. Therefore, in Network Function Virtualization (NFV)-aware environments, on-chip fast cache memories of a CPU of general-purpose hardware become critical to achieve high performance packet processing speeds of over tens of Gbps. Also, multiple types of applications and complex applications are executed in the same system simultaneously in carrier network systems, which require adequate cache memory capacities as well. In this paper, we propose a packet processing architecture that utilizes interleaved 3 Dimensional (3D)-stacked Dynamic Random Access Memory (DRAM) devices as off-chip Last Level Cache (LLC) in addition to several levels of dedicated cache memories of each CPU core. Entries of a lookup table are distributed in every bank and vault to utilize both bank interleaving and vault-level memory parallelism. Frequently accessed entries in 3D-stacked DRAM are also cached in on-chip dedicated cache memories of each CPU core. The evaluation results show that the proposed architecture reduces the memory access latency by 57%, and increases the throughput by 100% while reducing the blocking probability but about 10% compared to the architecture with shared on-chip LLC. These results indicate that 3D-stacked DRAM can be practical as off-chip LLC in parallel packet processing systems.
Bing LIU Zhengchun ZHOU Udaya PARAMPALLI
Inspired by an idea due to Levenshtein, we apply the low correlation zone constraint in the analysis of the weighted mean square aperiodic correlation. Then we derive a lower bound on the measure for quasi-complementary sequence sets with low correlation zone (LCZ-QCSS). We discuss the conditions of tightness for the proposed bound. It turns out that the proposed bound is tighter than Liu-Guan-Ng-Chen bound for LCZ-QCSS. We also derive a lower bound for QCSS, which improves the Liu-Guan-Mow bound in general.
Kohei WATANABE Yuma KOBAYASHI Yasuhiro KOIKE
Temperature-independent zero-zero-birefringence polymer (TIZZBP), which exhibits very small birefringence over the wide temperature range, is required to realize real-color images for displays, particularly vehicle-mounted displays. Previously, a TIZZBP was synthesized, but they did not put into practical use because of their too complex composition and low mechanical strength. In this paper, we propose a practical TIZZBP that has high heat resistance, high transparency and sufficient mechanical strength, using a simple binary copolymerization system. Our proposed novel polymer exhibits very low photoelastic birefringence and very low orientational birefringence. Both types of birefringence of this TIZZBP satisfy the negligible levels for displays, which are defined as follows: the absolute values of photoelastic coefficient and intrinsic birefringence are less than 1 ×10-12 Pa-1 and 1 ×10-3, respectively. In addition, temperature dependency of orientational birefringence was very low. Orientational birefringence satisfies the negligible level all over the temperature range from around -40°C to 85°C. This temperature range is important because it is the operational temperature range for vehicle-mounted display. Furthermore, our proposed novel TIZZBP showed high heat resistance, high transparency and sufficient mechanical strength. The glass transition temperature was 194°C. The total light transmittance and the haze value is more than 91% and less than 1%, respectively. The tensile strength of non-oriented films was 35 ~ 50 MPa. These results suggest our proposed novel TIZZBP has high practicality in addition to very low birefringence. Therefore, this TIZZBP film will be very useful for various displays including vehicle-mounted displays and flexible displays.
Zhenhui XU Tielong SHEN Daizhan CHENG
This paper studies the infinite time horizon optimal control problem for continuous-time nonlinear systems. A completely model-free approximate optimal control design method is proposed, which only makes use of the real-time measured data from trajectories instead of a dynamical model of the system. This approach is based on the actor-critic structure, where the weights of the critic neural network and the actor neural network are updated sequentially by the method of weighted residuals. It should be noted that an external input is introduced to replace the input-to-state dynamics to improve the control policy. Moreover, strict proof of convergence to the optimal solution along with the stability of the closed-loop system is given. Finally, a numerical example is given to show the efficiency of the method.
Sho KANAMARU Kazushi KAWAMURA Shu TANAKA Yoshinori TOMITA Nozomu TOGAWA
Ising machines have attracted attention, which is expected to obtain better solutions of various combinatorial optimization problems at high speed by mapping the problems to natural phenomena. A slot-placement problem is one of the combinatorial optimization problems, regarded as a quadratic assignment problem, which relates to the optimal logic-block placement in a digital circuit as well as optimal delivery planning. Here, we propose a mapping to the Ising model for solving a slot-placement problem with additional constraints, called a constrained slot-placement problem, where several item pairs must be placed within a given distance. Since the behavior of Ising machines is stochastic and we map the problem to the Ising model which uses the penalty method, the obtained solution does not always satisfy the slot-placement constraint, which is different from the conventional methods such as the conventional simulated annealing. To resolve the problem, we propose an interpretation method in which a feasible solution is generated by post-processing procedures. We measured the execution time of an Ising machine and compared the execution time of the simulated annealing in which solutions with almost the same accuracy are obtained. As a result, we found that the Ising machine is faster than the simulated annealing that we implemented.
Young-Woo KWON Sung-Mun PARK Joon-Young CHOI
We propose a system time synchronization method between ARM-based embedded Linux systems. The master Linux with reference clock sends its own system time to the slave Linux via Transmission Control Protocol communication along with a general-purpose input/output (GPIO) signal, and then the slave Linux corrects its own system time by the difference between its own system time at receiving the GPIO signal and the received reference time. The synchronization performance is significantly improved by compensating for the GPIO signal detection latency and the system time acquisition and setting latencies in Linux. These latencies are precisely measured by exploiting the function of Cycle Counter register in ARM coprocessor. Extensive experiments are performed with two ARM-based embedded Linux systems, and the results demonstrate the validity and performance of the proposed synchronization method.
This paper is focused on constructing even-length binary Z-complementary pairs (EB-ZCPs) with new length. Inspired by a recent work of Adhikary et al., we give a construction of EB-ZCPs with length 8N+4 (where N=2α 10β 26γ and α, β, γ are nonnegative integers) and zero correlation zone (ZCZ) width 5N+2. The maximum aperiodic autocorrelation sums (AACS) magnitude of the proposed sequences outside the ZCZ region is 8. It turns out that the generated sequences have low PAPR.
Daiki OGAWA Koichi KOBAYASHI Yuh YAMASHITA
A blockchain, which is well known as one of the distributed ledgers, has attracted in many research fields. In this paper, we discuss the effectiveness and limitation of a blockchain in distributed optimization. In distributed optimization, the original problem is decomposed, and the local problems are solved by multiple agents. In this paper, ADMM (Alternating Direction Method of Multipliers) is utilized as one of the powerful methods in distributed optimization. In ADMM, an aggregator is basically required for collecting the computation result in each agent. Using blockchains, the function of an aggregator can be contained in a distributed ledger, and an aggregator may not be required. As a result, tampering from attackers can be prevented. As an application, we consider energy management systems (EMSs). By numerical experiments, the effectiveness and limitation of blockchain-based distributed optimization are clarified.
Ryutaro FUJIKAWA Tomoyuki TOGAWA Toshimichi SAITO
This paper studies a novel approach to analysis of switched dynamical systems in perspective of bifurcation and multiobjective optimization. As a first step, we analyze a simple switched dynamical system based on a boost converter with photovoltaic input. First, in a bifurcation phenomenon perspective, we consider period doubling bifurcation sets in the parameter space. Second, in a multiobjective optimization perspective, we consider a trade-off between maximum input power and stability. The trade-off is represented by a Pareto front in the objective space. Performing numerical experiments, relationship between the bifurcation sets and the Pareto front is investigated.
Kazumune HASHIMOTO Masako KISHIDA Yuichi YOSHIMURA Toshimitsu USHIO
In this paper, we investigate a model-free design of decentralized event-triggered mechanism for networked control systems (NCSs). The approach aims at simultaneously tuning the optimal parameters for the controller and the event-triggered condition, such that a prescribed cost function can be minimized. To achieve this goal, we employ the Bayesian optimization (BO), which is known to be an automatic tuning framework for finding the optimal solution to the black-box optimization problem. Thanks to its efficient search strategy for the global optimum, the BO allows us to design the event-triggered mechanism with relatively a small number of experimental evaluations. This is particularly suited for NCSs where network resources such as the limited life-time of battery powered devices are limited. Some simulation examples illustrate the effectiveness of the approach.
Yuji ARAKI Kentaro MITA Koichi ICHIGE
We propose an iterative single-image haze-removal method that first divides images with haze into regions in which haze-removal processing is difficult and then estimates the ambient light. The existing method has a problem wherein it often overestimates the amount of haze in regions where there is a large distance between the location the photograph was taken and the subject of the photograph; this problem prevents the ambient light from being estimated accurately. In particular, it is often difficult to accurately estimate the ambient light of images containing white and sky regions. Processing those regions in the same way as other regions has detrimental results, such as darkness or unnecessary color change. The proposed method divides such regions in advance into multiple small regions, and then, the ambient light is estimated from the small regions in which haze removal is easy to process. We evaluated the proposed method through some simulations, and found that the method achieves better haze reduction accuracy even than the state-of-the art methods based on deep learning.
Makoto YAMASHITA Naoki HAYASHI Shigemasa TAKAI
This paper considers a distributed subgradient method for online optimization with event-triggered communication over multi-agent networks. At each step, each agent obtains a time-varying private convex cost function. To cooperatively minimize the global cost function, these agents need to communicate each other. The communication with neighbor agents is conducted by the event-triggered method that can reduce the number of communications. We demonstrate that the proposed online algorithm achieves a sublinear regret bound in a dynamic environment with slow dynamics.
Yoshihiro OSAKABE Shigeo SATO Hisanao AKIMA Mitsunaga KINJO Masao SAKURABA
Utilizing the enormous potential of quantum computers requires new and practical quantum algorithms. Motivated by the success of machine learning, we investigate the fusion of neural and quantum computing, and propose a learning method for a quantum neural network inspired by the Hebb rule. Based on an analogy between neuron-neuron interactions and qubit-qubit interactions, the proposed quantum learning rule successfully changes the coupling strengths between qubits according to training data. To evaluate the effectiveness and practical use of the method, we apply it to the memorization process of a neuro-inspired quantum associative memory model. Our numerical simulation results indicate that the proposed quantum versions of the Hebb and anti-Hebb rules improve the learning performance. Furthermore, we confirm that the probability of retrieving a target pattern from multiple learned patterns is sufficiently high.
Takahiro MATSUMOTO Hideyuki TORII Yuta IDA Shinya MATSUFUJI
In this paper, we propose new generation methods of two-dimensional (2D) optical zero-correlation zone (ZCZ) sequences with the high peak autocorrelation amplitude. The 2D optical ZCZ sequence consists of a pair of a binary sequence which takes 1 or 0 and a bi-phase sequence which takes 1 or -1, and has a zero-correlation zone in the two-dimensional correlation function. Because of these properties, the 2D optical ZCZ sequence is suitable for optical code-division multiple access (OCDMA) system using an LED array having a plurality of light-emitting elements arranged in a lattice pattern. The OCDMA system using the 2D optical ZCZ sequence can be increased the data rate and can be suppressed interference by the light of adjacent LEDs. By using the proposed generation methods, we can improve the peak autocorrelation amplitude of the sequence. This means that the BER performance of the OCDMA system using the sequence can be improved.
Yuki NISHIO Osamu TAKYU Hayato SOYA Keiichiro SHIRAI Mai OHTA Takeo FUJII
Dynamic spectrum access (DSA) exploits vacant frequency resources via distributed wireless access. The two nodes of DSA, master and slave, access different channels, and thus, cannot communicate with each other. To compensate for the access channel mismatch between the two nodes, a rendezvous channel, which exchanges control signals between two nodes, has been considered. The rendezvous channel based on channel-occupancy ratio (COR) adaptively constructs the channel in accordance with the channel occupancy of other systems, and both a high-speed rendezvous channel and high usage efficiency of the frequency resource are accomplished owing to exploitation of the vacant channel. In the rendezvous channel based on COR, the master and slave recognize the channel with minimum measured COR as the superior channel. As the master sends the control signals through the superior channel recognized by the master, the slave accesses to the superior channel recognized by the slave with higher access rate than to the other channels. As a result, the slave can receive the control signals with highly probability and thus high speed rendezvous channel is achieved. If the master and the slave recognize the different channel as the superior channel, the access rate to the other channel should be larger. This is because the slave obtains the opportunity of receiving the control signals through the different channel from the superior channel recognized by slave and thus the high probability that the slave can receive the control signals is maintained. Therefore, the access rate of slave should be constructed in accordance with the recognition of superior channel by master and slave. In this paper, the access rate of slave to the superior channel is optimally constructed using the analyzed probability of completion of rendezvous channel. The analysis of the probability of completion of rendezvous channel includes the recognition of superior channel by master and slave. Even if the master and the slave recognize the different channel, the constructed access rate of slave can maintain the high speed rendezvous channel. From the theoretical analysis and computer simulation, the rendezvous channel based on COR with the optimal access rate to the channel with the lowest COR achieves reduced time for the rendezvous channel.
Longfei CHEN Yuichi NAKAMURA Kazuaki KONDO Dima DAMEN Walterio MAYOL-CUEVAS
We propose a novel framework for integrating beginners' machine operational experiences with those of experts' to obtain a detailed task model. Beginners can provide valuable information for operation guidance and task design; for example, from the operations that are easy or difficult for them, the mistakes they make, and the strategy they tend to choose. However, beginners' experiences often vary widely and are difficult to integrate directly. Thus, we consider an operational experience as a sequence of hand-machine interactions at hotspots. Then, a few experts' experiences and a sufficient number of beginners' experiences are unified using two aggregation steps that align and integrate sequences of interactions. We applied our method to more than 40 experiences of a sewing task. The results demonstrate good potential for modeling and obtaining important properties of the task.