M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.

The paper presents a topology-oriented robust algorithm for the incremental construction of line arrangements. In order to achieve a robust implementation, the topological and geometrical computations are strictly separated. The topological part is proved to be reliable without any assumption on the accuracy of the geometrical part. A self-correcting property is introduced to minimize the effect of numerical errors. Computational experiments show how the self-correcting property works, and we also discuss some applications of the algorithm.

A linkage is a collection of line segments, called bars, possibly joined at their ends, called joints. A planar reconfiguration of a linkage is a continuous motion of their bars, preserving the length of each bar and disallowing bars to cross. In this paper, we introduce a class of linkages, called "monotone trees," and give a method for reconfiguring a monotone tree to a straight line. If the tree has n joints, then the method takes at most n-1 moves, each of which uses two joints. We also obtain an algorithm to find such a method in time O(n log n), using space O(n). These time and space complexities are optimal.

In this paper we deal with Voronoi diagram in simply connected complete manifold with non positive curvature, called Hadamard manifold. We prove that a part of the Voronoi diagram can be characterized by hyperbolic Voronoi diagram. Voronoi diagram in simply connected complete manifold is also characterized for a given set of points satisfying a distance condition.

Most conventional studies on self-stabilization have been indifferent to the vulnerability under convergence. This paper investigates how mutual exclusion property can be achieved in self-stabilizing rings even for illegitimate configurations. We present a new method which uses a state with a large state space to detect faults. If some faults are detected, every process is reset and not given a privilege. Even if the reset values are different between processes, our protocol mimics the behavior of Dijkstra's unidirectional K-state protocol. Then we have a fast and safe mutual exclusion protocol. Simulation study also examines its performance.

A family F of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. We say that a family F of permutations on {0,1,. . . ,n-1} is min-wise independent if for any X {0,1,. . . ,n-1} and any x X, Pr[min {π(X)} = π(x)]= ||X||^-1 when π is chosen uniformly at random from F, where ||A|| is the cardinality of a finite set A. We also say that a family F of permutations on {0,1,. . . ,n-1} is d-wise independent if for any distinct x₁,x₂,. . . ,x_d {0,1,. . . , n-1} and any distinct y₁,y₂,. . . ,y_d {0,1,. . . , n-1}, Pr[_i=1^d π(x_i) = π(y_i)]= 1/{n(n-1)・・・ (n-d+1)} when π is chosen uniformly at random from F (note that nontrivial constructions of d-wise independent family F of permutations on {0,1,. . . ,n-1} are known only for d=2,3). Recently, Broder, et al. showed that any family F of pairwise (2-wise) independent permutations behaves close to a family of min-wise independent permutations, i.e., for any X {0,1,. . . ,n-1} such that 3 ||X||=k n-2 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-1)}; (upper bound) Pr[min {π(X)}=π(x)] O(1/k). In this paper, we extend these bounds to 3-wise independent permutation family and show that any family of 3-wise independent permutations behaves closer to a family of min-wise independent permutations, i.e., for any X {0,1,. . . ,n-1} such that 4 ||X||=k n-3 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k-2)²}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).

A radio network is a distributed system with no central shared resource, consisting of n stations each equipped with a radio transceiver. One of the most important parameters to evaluate protocols in the radio networks is the number of awake time slots in which each individual station sends/receives a data packet. We are interested in devising energy-efficient initialization protocols in the single-hop radio network (RN, for short) that assign unique IDs in the range [1,n] to the n stations using few awake time slots. It is known that the RN can be initialized in O(log log n) awake time slots, with high probability, if every station knows the number n of stations in the RN. Also, it has been shown that the RN can be initialized in O(log n) awake time slots even if no station knows n. However, it has been open whether the initialization can be performed in O(log log n) awake time slots when no station knows n. Our main contribution is to provide the breakthrough: we show that even if no station knows n, the RN can be initialized by our protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log log n) time slots. We then go on to design an initialization protocol for the k-channel RN that terminates, with high probability, in O(n/k + (log n)²) time slots with no station being awake for more than O(log log n) time slots.

For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

Spiral hashing is a well known dynamic hashing algorithm. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.

A VLSI algorithm for division in GF(2^m) with the canonical basis representation is proposed. It is based on the extended Binary GCD algorithm for GF(2^m), and performs division through iteration of simple operations, such as shifts and bitwise exclusive-OR operations. A divider in GF(2^m) based on the algorithm has a linear array structure with a bit-slice feature and carries out division in 2m clock cycles. The amount of hardware of the divider is proportional to m and the depth is a constant independent of m.

In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.

Sports scheduling concerns how to construct a schedule of a sports competition mathematically. Many sports competitions are held as round-robin tournaments. In this paper, we consider a particular class of round-robin tournaments. We report some properties of round-robin tournaments and enumerate home-away tables satisfying some practical requirements by computer search.

In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.

In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex v as a sink in the network such that we can send all the initial suplies to v as quick as possible. This problem can be regarded as a dynamic flow version of the 1-center problem in a tree network. We present an O(n²) time algorithm for the sink location problem, where n is the number of vertices in the network.

Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.

If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph is useful for identifying critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n) processors on CREW PRAM for finding all hinge vertices of a trapezoid graph.

We present a simple solution to secretly sharing a factoring witness (for given N) in a publicly-verifiable manner. Compared to the previous PVSS schemes to secretly sharing a factoring witness, the scheme enjoys the following properties: (1) the formal proofs of security can be given; (2) it is designed to be conceptually simpler; (3) it needs fewer communicated bits and, if not-so low exponent RSA (e.g., e > 2¹⁹+1) is used in the previous schemes, fewer computations; (4) no general multi-party computation is required in the preparation phase.

Since the invention of the RSA scheme, a lot of public-key encryption and signature schemes based on the intractability of integer factoring have been proposed. Most employ integers of the form N = p q, such as the RSA scheme, but some employ integers of the form N = p^r q. It has been reported that RSA decryption speed can be greatly improved by using N = p^r q integers for large r. On the other hand, Boneh et al. proposed a novel integer factoring method for integers such as N = p^r q for large r. This factoring algorithm, the so-called Lattice Factoring Method, is based on the LLL-algorithm. This paper proposes a new method for factoring integers of the form N = p^r q for large r and gives a new characterization of r such that factoring integers N = p^r q is easier. More precisely, the proposed method strongly depends on the size and smoothness of the exponent, r. The theoretical consideration of and implementation of our method presented in this paper show that if r satisfies a certain condition our method is faster than both Elliptic Curve Method and Lattice Factoring Method. In particular, the theoretical consideration in this paper mainly employs the techniques described in the excellent paper by Adleman, Pomerance and Rumely that addresses primality testing.

An English auction is the most familiar type of auctions. Generally, an electronic auction has mainly two entities, the registration manager (RM) who treats the registration of bidders, and the auction manager (AM) who holds auctions. Before starting an auction, a bidder who wants to participate in English auction is registered to RM with her/his information. An electronic English auction protocol should satisfy the following nine properties, (a) Anonymity, (b) Traceability, (c) No framing, (d) Unforgeability, (e) Fairness, (f) Verifiability, (g) Unlinkability among plural auctions, (h) Linkability in an auction, and (i) Efficiency of bidding. Furthermore from the practical point of view we add two properties (j) Easy revocation and (k) One-time registration. A group signature is adapted to an English auction in order to satisfy (a), (b), and (f). However such a direct adoption suffers from the most critical drawback of efficiency in group signatures. In this paper we propose more realistic electronic English auction scheme, which satisfies all of these properties without using a group signature. Notable features of our scheme are: (1) both of bidding and verification of bids are done quite efficiently by introducing a bulletin board, (2) both properties (j) Easy revocation and (k) One-time registration are satisfied.

A kind of online edge-coloring problems on bipartite graphs is considered. The input is a graph (typically with no edges) and a sequence of operations (edge addition and edge deletion) under the restriction that at any time the graph is bipartite and degree-bounded by k, where k is a prescribed integer. At the time of edge addition, the added edge can be irrevocably assigned a color or be left uncolored. No other coloring or color alteration is allowed. The problem is to assign colors as many times as possible using k colors. Two algorithms are presented: one with competitiveness coefficient 1/4 against oblivious adversaries, and one with competitiveness coefficient between 1/4 and 1/2 with the cost of requiring more random bits than the former algorithm, also against oblivious adversaries.

We consider the polymatroid packing and covering problems. The polynomial time algorithm with the best approximation bound known for either problem is the greedy algorithm, yielding guaranteed approximation factors of 1/k for polymatroid packing and H(k) for polymatroid covering, where k is the largest rank of an element in a polymatroid, and H(k)=Σ_i=1^k 1/i is the kth Harmonic number. The main contribution of this note is to improve these bounds by slightly extending the greedy heuristics. Specifically, it will be shown how to obtain approximation factors of 2/(k+1) for packing and H(k)-1/6 for covering, generalizing some existing results on k-set packing, matroid matching, and k-set cover problems.

This letter treats computational complexity of bounded asymmetric choice (AC) net. AC net is a subclass of Petri net that properly includes the class of well-known extended free choice net. It is shown that satisfiability problem of Boolean expressions is polynomial time reducible to liveness problem of bounded AC nets. This implies that the problem is NP-hard.

We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2^k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.

An all-or-nothing transform (AONT), which has been proposed by Rivest, is one of encryption modes. The AONT is intended to increase the cost of brute-fore attacks on a block cipher. This paper provides the revised definition of an unconditionally secure AONT, and shows the instance of an optimal unconditionally secure AONT. In addition, we propose a computationally secure AONT such that any information on a message cannot be obtained regardless of the position of the lost block due to a linear code.

In this paper, we present a method to analyze the steady-state performance of a complex coefficient adaptive IIR notch filter which is useful for the rejection of multiple narrow-band interferences from broad-band signals in quadrature phase shift keying (QPSK) spread-spectrum communication systems. The adaptive notch filter based on the simplified gradient algorithm is considered. Analytical expressions have been developed for the conditional mean and variance of notch filter output. The signal-to-noise ratio improvement factor is also obtained from which the validity of the use of the notch filter can be concluded. Finally, the results of computer simulations are shown which confirm the theoretical predictions.

Adaptive Fourier analysis of sinusoidal signals in noise is of essential importance in many engineering fields. So far, many adaptive algorithms have been developed. In particular, a filter bank based algorithm called constrained notch Fourier transform (CNFT) is very attractive in terms of its cost-efficiency and easily controllable performance. However, its performance becomes poor when the signal frequencies are non-uniformly spaced (or spaced with unequal intervals) in the frequency domain. This is because the estimates of the discrete Fourier coefficients (DFCs) in the CNFT are inevitably corrupted by sinusoidal disturbances in such a case. This paper proposes, at first, a modified CNFT (MCNFT), to compensate the performance of the CNFT for noisy sinusoidal signals with known and non-uniformly spaced signal frequencies. Next, performance analysis of the MCNFT is conducted in detail. Closed form expression for the steady-state mean square error (MSE) of every DFC estimate is derived. This expression indicates that the MSE is proportional to the variance of the additive noise and is a complex function of both the frequency of each frequency component and the pole radius of the bandpass filter used in the filter bank. Extensive simulations are presented to demonstrate the improved performance of the MCNFT and the validity of the analytical results.

Practical image restoration filters usually include a parameter that controls regularizability, trade-off between fidelity of a restored image and smoothness of it, and so on. Many criteria for choosing such a parameter have been proposed. However, the relation between these criteria and the squared error of a restored image, which is usually used to evaluate the restoration performance, has not been theoretically substantiated. Sugiyama and Ogawa proposed the subspace information criterion (SIC) for model selection of supervised learning problems and showed that the SIC is an unbiased estimator of the expected squared error between the unknown model function and an estimated one. They also applied it to restoration of images. However, we need an unbiased estimator of the unknown original image to construct the criterion, so it can not be used for general situations. In this paper, we present a modified version of the SIC as a new criterion for choosing a parameter of image restoration filters. Some numerical examples are also shown to verify the efficacy of the proposed criterion.

This paper presents effective methods to calculate dual frame of the short-time Fourier expansion (STFE) in l²(Z). Based on a relationship between the prototype window used for generating a frame and the dual prototype window used for generating a dual frame in the STFE, two useful numerical methods with a finite frame operator are proposed to obtain finite support dual frames in time domain formulation. The methods can be used to construct the multiple STFE (MSTFE) suitable for a time-frequency analysis, synthesis and coding of discrete-time nonstationary signals. Numerical simulation results are given to verify the effectiveness of the calculation of dual frame.

Conventional system models such as the finite impulse response (FIR) model, autoregressive external input (ARX) model, time delay neural network (TDNN), and recurrent neural network (RNN) depend on short-term memory when modeling a discrete time system. However, short-term memory can be inefficient with a varying appearance speed of I/O data. This inefficiency is referred to herein as the Varying Appearance Speed Problem (VASP) and demonstrated by analyzing impulse and frequency responses. Simulation results indicate that the varying appearance speed leads to asymmetrical cycles. Unable to prevent the memory effect from extensively disturbing the next output cycle, conventional models simulate the systems inaccurately. A solution using rate independent memory is then proposed. Only concerned with the previous extreme inputs, rate independent memory differs from short-term memory and potentially prevents a system model from the impact of varying appearance speeds. To demonstrate the VASP and verify the proposed model, this study conducts three experiments, i.e. (a) learning random step trajectories of circular and trefoil shapes, (b) modeling the relationship between the economic leading and coincident indexes, (c) simulating the connection between the ground-water level and land subsidence. In contrast to conventional models, the model presented here performs better in terms of mean square errors.

In this paper, we present the division algorithm (DA) for the computation of b=c/a over GF(2^m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB^*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.

In this paper, a new family of interconnection networks which we call the Incrementally Extensible Twisted Cube (IETQ) is proposed. The topology of this network is a novel generalization of the twisted cube. It inherits all the merits but without the limitations owned by a twisted cube. First, this proposed IETQ is incrementally extensible and can be adapted for use in any number of nodes; therefore, this network is particularly well suited for the design of a distributed communication network with an arbitrary number of nodes. Second, the vertex connectivity of IETQ is n. Measured by this vertex connectivity, we demonstrate that this network is optimally fault-tolerant . And it is almost regular, because the difference between the maximum and minimum degree of any node in an IETQ is at most one. A shortestpath routing algorithm for IETQ is proposed to generate path for any given pair of vertices in the network. Third, comparing with most of the other competitors, the diameter of this IETQ network is only half in size. This low diameter helps to reduce the internode communication delay. Moreover, IETQ also possesses the property of a pancyclic network. This attractive property would enable us to map rings of any length into the proposed network.

We consider diagnosability of butterfly networks under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura discussed characterization of diagnosable systems under the comparison approach, and designed a polynomial time algorithm to identify the faulty processors. However, for a general system, it is not algorithmically easy to determine its diagnosability. This paper proposes two comparison schemes for generating syndromes on butterfly networks, and determine the diagnosability of the network.

Gallager has defined an ensemble of regular low density parity check (LDPC) codes for deriving the ensemble performance of regular LDPC codes. The ensemble is called the Gallager ensemble. In this paper, we define a new ensemble of LDPC codes, called extended Gallager ensemble, which is a natural extension of the Gallager ensemble. It is shown that an extended Gallager ensemble has potential to achieve larger typical minimum distance ratio than that of the original Gallager ensemble. In particular, the extended Gallager ensembles based on the Hamming and extended Hamming codes have typical minimum distance ratio which is very close to the asymptotic Gilbert-Varshamov bound. Furthermore, decoding performance of an instance of an extended Gallager ensemble, called an extended LDPC code, has been examined by simulation. The results show good block error performance of extended LDPC codes.

This letter proposes a design methodology of a capacitor for a switched capacitor filter. The capacitor design method makes the capacitor accurate to the capacitance ratio and insensitive to the process deviation. The SCF designed is used for the PCM CODEC filter and the deviation of the frequency characteristic is below 0.05 dB for a process deviation 0.5 µm in 5 µm CMOS process.

In this letter, we present an output feedback controller design technique for uncertain discrete time systems with multiple time-delays. Based on Lyapunov second method, a sufficient condition for the robust stability of the system with a dynamic controller is derived in terms of the linear matrix inequality (LMI) with respect to design variables. The solutions of the LMIs can be easily obtained using existing efficient convex optimization techniques.

In 1998, Fan and Lei proposed a partially blind signature scheme that could reduce the computation load and the size of the database for electronic cash systems. In this Letter, we show that their scheme could not meet the untraceability property of a blind signature.

This letter presents the empirical error performance of combining method of a binary numerical code and a single error correcting code on Gaussian channel by belief propagation (BP) decoding algorithm. The numerical codes mentioned here are constructed with any symbol value and have the parity check matrices in reduced-echelon form whose elements are binary (0 and 1). The simulation results show that the method yields good decoding error performance for medium code lengths.