Masahiko SHIMOMURA Mikio KUDO Hiroaki MOHRI
The vehicle routing and facility location fields are well-developed areas in management science and operations research application. There is an increasing recognition that effective decision-making in these fields requires the adoption of optimization software that can be embedded into a decision support system. In this paper, we describe the implementation details of our software components for solving the vehicle routing and facility location problems.
Koichi IIYAMA Takahiro MAEDA Saburo TAKAMIYA
We describe FMCW reflectometry for characterization of long optical fibers by using an external-cavity laser diode as a light source. Since the optical path difference between the reference beam and the reflected beam from the optical fiber under test is much longer than the coherence length of the light source, the reference and the reflected beams are phase-decorrelated. As a result, the beat spectrum between the reference and the reflected beams is measured. In the phase-decorrelated FMCW reflectomety, the spatial resolution is enhanced by narrowing the spectral linewidth of the light source and increasing the repetition frequency of the optical frequency sweep as well as increasing the chirping range of the optical frequency sweep. In the experiments, an external-cavity DFB laser is used as a narrow linewidth light source, and the optical frequency is swept by minute modulation of the external cavity length. Long single mode optical fibers are characterized, and the maximum measurement range of 80 km is achieved, and the spatial resolutions of 46 m, 100 m and 2 km are achieved at 5 km, 11 km and 80 km distant, respectively. The Rayleigh backscattering is clearly measured and the propagation loss of optical fiber is also measured. The optical gain of an erbium-doped optical fiber amplifier (EDFA) is also estimated from the change in the Rayleigh backscattering level in the optical fiber followed after the EDFA.
Nozomu TOGAWA Masao YANAGISAWA Tatsuo OHTSUKI
In digital signal processing, bit width of intermediate variables should be longer than that of input and output variables in order to execute intermediate operations with high precision. Then a processor core for digital signal processing is required to have two types of register files, one of which is used by input and output variables and the other one is used by intermediate variables. This paper proposes a hardware/software cosynthesis system for digital signal processor cores with two types of register files. Given an application program and its data, the system synthesizes a hardware description of a processor core, an object code running on the processor core, and software environments. A synthesized processor core can be composed of a processor kernel, multiple data memory buses, hardware loop units, addressing units, and multiple functional units. Furthermore it can have two types of register files RF1 and RF2. The bit width and number of registers in RF1 or RF2 will be determined based on a given application program. Thus a synthesized processor core will have small area with keeping high precision of intermediate operations compared with a processor core with only one register file. The experimental results demonstrate the effectiveness of the proposed system.
This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.
Younggeun HAN Chang-Seok KIM Un-Chul PAEK Youngjoo CHUNG
We will discuss performance optimization of strain and temperature sensors based on long period fiber gratings (LPFGs) through control of the temperature sensitivity of the resonant peak shifts. Distinction between the effects of strain and temperature is a major concern for applications to communication and sensing. This was achieved in this work by suppressing or enhancing the temperature sensitivity by adjusting the doping concentrations of GeO2 and B2O3 in the core or cladding. The LPFGs were fabricated with a CO2 laser by the mechanical stress relaxation and microbending methods. The optimized temperature sensitivities were 0.002 nm/ for the suppressed case and 0.28 nm/ for the enhanced case, respectively. These LPFGs were used for simultaneous measurement of strain and temperature. The result indicates the rms errors of 23 µstrain for the strain and 1.3 for the temperature.
Saeed PILEVAR Trevor W. MACDOUGALL Christopher C. DAVIS
A general analytical expression for describing the growth of the resonant peak wavelengths of long period gratings is derived. The theoretical calculations explain the shift of peak loss wavelengths in the direction of either shorter or longer wavelengths as the induced index change of grating increases. We have calculated and experimentally verified the sensitivity of the resonant peak wavelengths with respect to an overlay index for various grating periods. It is shown that the center wavelength shift of the claddding modes depends strongly on the grating period and the claddding mode order.
Takao ASANO Kenichiro IWAMA Hideyuki TAKADA Yoshiko YAMASHITA
For NP-hard combinatorial optimization problems, approximation algorithms with high performances have been proposed. In many of these algorithms, mathematical programming techniques have been used and proved to be very useful. In this survey, we present recent mathematical programming techniques as well as classic fundamental techniques, by showing how these techniques are used in designing high-quality approximation algorithms for NP-hard combinatorial optimization problems.
Tetsu SOH Kouji WADA Osamu HASHIMOTO
An epoxy-modified urethane rubber mixed with carbon particles is now chosen as the millimeter-wave absorber material in our study. The absorption characteristics of the absorber is measured under temperature changes. The weatherability of our absorber is also clarified based on absorption characteristics, thickness and hardness of the sample. As a result of the temperature characteristics of the absorber, the difference of the maximum absorption frequency under temperature changes is about 1 GHz, however the absorption of 20 dB or more is obtained between 54 and 58 GHz. The result of accelerated artificial exposure test is that 2.8% of the thickness of our sample is shrunk after 1000 hour exposure, and the hardness of rubber is hardened with increasing test time. It is also confirmed that the deterioration of the absorption ranges from 1 to 3 dB, although the absorption of about 20 dB is kept at the frequency range. As a consequence, it is confirmed that the wave absorber using the epoxy-modified urethane rubber mixed with carbon particles has good weatherability including our desired temperature characteristics, and it is suitable for outdoor use.
Leszek R. JAROSZEWICZ Aleksander KIEZUN Ryszard SWILLO
In the paper, a theoretical and experimental investigation of a new type of the in-line optical fiber ellipsometer is described. The discussed device, based on the Sagnac interferometer, has the possibility to detect the changes of full polarisation state. The detection of the polarisation state in real time by a system containing standard single-mode fiber and an appropriate applied modulation technique is a new system property. The device uses interferometric measurement technique based on the fourth Fresnel-Arago's condition, which secures very good system accuracy and stability, also presented in the paper.
Tetsushi WATANABE Osami WADA Takuya MIYASHITA Ryuji KOGA
This paper explains a mechanism of common-mode generation on a printed circuit board with a narrow ground pattern. A transmission line has its value of degree of unbalance. At a connection point of two transmission lines having different degrees of unbalance, common mode voltage is generated proportional to the difference, and it drives common mode current. The authors propose a method to evaluate common mode current distribution and verify it by measurement. Although calculated common mode current is larger than measured one by a few dBs, both of them are proportional to the degree of unbalance. An EMI reduction technique, 'unbalance matching,' is also proposed.
A short review of distributed and multiplexed sensor technology, based on fibre gratings, is given. This is followed by details of more specific work in this area at the University of Southampton, particularly grating fabrication, distributed and multiplexed addressing and important practical aspects such as temperature and strain discrimination. The paper concludes with a short discussion of the problems that must be avoided in order to construct viable systems for engineering requirements.
Given N real weights w1, w2, . . . , wN stored in one-dimensional array, we consider the problem for finding an optimal interval I [1, N] under certain criteria. We shall review efficient algorithms developed for solving such problems under several optimality criteria. This problem can be naturally extended to two-dimensional case. Namely, given a NN two-dimensional array of N2 reals, the problem seeks to find a subregion of the array (e. g. , rectangular subarray R) that optimizes a certain objective function. We shall also review several algorithms for such problems. We shall also mention applications of these problems to region segmentation in image processing and to data mining.
Triangulations have been one of main research topics in computational geometry and have many applications in computer graphics, finite element methods, mesh generation, etc. This paper surveys properties of triangulations in the two- or higher-dimensional spaces. For triangulations of the planar point set, we have a good triangulation, called the Delaunay triangulation, which satisfies several optimality criteria. Based on Delaunay triangulations, many properties of planar triangulations can be shown, and a graph structure can be constructed for all planar triangulations. On the other hand, triangulations in higher dimensions are much more complicated than in planar cases. However, there does exist a subclass of triangulations, called regular triangulations, with nice structure, which is also touched upon.
Maximum Satisfiability Problem (MAX SAT) is one of the most natural optimization problems. Since it is known to be NP-hard, approximation algorithms have been considered. The aim of this survey is to show recent developments of approximation algorithms for MAX SAT.
A reliable and automatic parameter extraction technique for DFB lasers is developed. The parameter extraction program which is named "LAPAREX" is able to determine many device parameters from a measured sub-threshold spectrum only, including gain- and index-coupling coefficients, and spatial phases of the grating at front and rear facets. Injection current dependence of coupling coefficients in a gain-coupled DFBlaser is observed, for the first time, by making use of it.
Tadashi ICHIKAWA Manabu KAGAMI Hiroshi ITO
This paper reports the performance of an AC-voltage sensor with a LiNbO3 integrated retroreflective structure based on the Y-junction Mach-Zehnder interferometer. This structure is capable of realizing a low-cost sensor chip because of the small chip size and single optical-fiber connection. In the sensitivity and frequency response evaluation, detection sensitivities of 6.3 µ V / Hz have been measured with a frequency response from 6 Hz to 2 GHz. These measurement limitations were also analyzed theoretically and compared with the experimental results. This unique sensor enables precise voltage measurement in an EMI environment, even inside a computer.
Shigeru MASUYAMA Shin-ichi NAKAYAMA
This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapezoid graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and the coloring problem on trapezoid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournament graphs are adopted as working examples.
Tsuyoshi IDEGUCHI Hiroaki KOGA Yoshifumi SHIMOSHIO
Metallic pair lines transmitting high-frequency information signals above several tens MHz are often used without being twisted, as flat floor cable installed in buildings, ribbon-type cables installed in computer equipment, and traces in printed circuit boards. However, the conversion characteristics of untwisted unbalanced metallic pair lines connecting unbalanced circuits have not been investigated over a wide range of frequencies in the MHz region. First, we developed a method to estimate effective power conversion factors using a cascade connection of F matrices, where the unbalance in impedance and admittance of each pair line is distributed uniformly along the line. As a result some useful information was obtained about the balance-unbalance conversion characteristics of the effective power which can be used to suppress EMI phenomena in wiring, especially over several decades of high frequencies. Next, we attempted to apply the conversion characteristics of untwisted unbalanced pair lines obtained at frequencies below several MHz to techniques for searching for the return circuits of conductors installed in buildings. It was clarified experimentaly that the depth of the equivalent ground plane can be estimated by comparing the measured conversion values of TV feeder lines installed at the place being tested with reference values measured in advance on a copper plate .
We review public-key cryptosystems from lattice problems, which are inspired by Ajtai's remarkable result, and consider their security from the point of view of both theory and practice. We also survey recent results on the power of the lattice reduction algorithm in cryptanalysis.
A new sensing method for measuring directly flow velocity by using low coherence interference techniques is proposed and demonstrated. In this method, a temporally fluctuating signal, not the Doppler frequency shift, is detected. Theoretical analysis shows that a spectrum of light backscattered from a particle takes a Gaussian form whose width is simply proportional to the flow velocity. The measured velocity is in good agreement with the actual flow velocity derived from the flow rate. The dynamic range of this sensing method is governed by the frequency range of the FFT processor used and is estimated to be 1.4 10-4 14 m/s. The depth position can be adjusted with an accuracy of approximately 30 µm which is determined by the coherence length of the light source. The velocity distribution along the depth is easily measured by changing mechanically the length of the reference arm in the low coherence interferometer.