In the online removable knapsack problem, a sequence of items, each labeled with its value and its size, is given one by one. At each arrival of an item, a player has to decide whether to put it into a knapsack or to discard it. The player is also allowed to discard some of the items that are already in the knapsack. The objective is to maximize the total value of the knapsack. Iwama and Taketomi gave an optimal algorithm for the case where the value of each item is equal to its size. In this paper we consider a case with an additional constraint that the capacity of the knapsack is a positive integer N and that the sizes of items are all integral. For each positive integer N, we design an algorithm and prove its optimality. It is revealed that the competitive ratio is not monotonic with respect to N.

Electric contact is one of the most important noise sources of electromagnetic noise. Hence, the noise of contact switching has been researched from various points of view with respect to the generation mechanism and properties. However, many phenomena have been remained not being investigated yet. In this paper, we describe our recent investigations about characteristics of the induced noise that is produced by the break of silver contact. The number of TTL IC's malfunction in the relay switching are counted under conditions of inductive load (10mH), circuit current (0.1-2A), and low source voltage (24V). From this experimental results, it became clear that the rate of malfunction decreased with increasing circuit current. To clarify its phenomenon, the circuit current dependence of the induced noise voltage was measured. It was observed that the level of induced noise voltage became the maximum in the current range of 0.2-1A. This property is discussed by the occurrence mechanism of each discharge mode on the break of contacts and the observation of induced noise corresponding to its mode.

The construction of a Huffman code can be understood as the problem of finding a full binary tree such that each leaf is associated with a linear function of the depth of the leaf and the sum of the function values is minimized. Fujiwara and Jacobs extended this to a general function and proved the extended problem to be NP-hard. The authors also showed the case where the functions associated with leaves are each non-decreasing and convex is solvable in polynomial time. However, the complexity of the case of non-decreasing non-convex functions remains unknown. In this paper we try to reveal the complexity by considering non-decreasing non-convex functions each of which takes the smaller value of either a linear function or a constant. As a result, we provide a polynomial-time algorithm for two subclasses of such functions.

We consider a problem as follows: Given unit weights arriving in an online manner with the total cardinality unknown, upon each arrival we decide where to place it on the unit circle in $mathbb{R}^{2}$. The objective is to set the center of mass of the placed weights as close to the origin as possible. We apply competitive analysis defining the competitive difference as a performance measure. We first present an optimal strategy for placing unit weights which achieves a competitive difference of $rac{1}{5}$. We next consider a variant in which the destination of each weight must be chosen from a set of positions that equally divide the unit circle. We give a simple strategy whose competitive difference is 0.35. Moreover, in the offline setting, several conditions for the center of mass to lie at the origin are derived.

Coalition Structure Generation (CSG) means partitioning agents into exhaustive and disjoint coalitions so that the sum of values of all the coalitions is maximized. Solving this problem could be facilitated by employing some compact representation schemes, such as marginal contribution network (MC-net). In MC-net, the CSG problem is represented by a set of rules where each rule is associated with a real-valued weights, and the goal is to maximize the sum of weights of rules under some constraints. This naturally leads to a combinatorial optimization problem that could be solved with weighted partial MaxSAT (WPM). In general, WPM deals with only positive weights while the weights involved in a CSG problem could be either positive or negative. With this in mind, in this paper, we propose an extension of WPM to handle negative weights and take advantage of the extended WPM to solve the MC-net-based CSG problem. Specifically, we encode the relations between each pair of agents and reform the MC-net as a set of Boolean formulas. Thus, the CSG problem is encoded as an optimization problem for WPM solvers. Furthermore, we apply this agent relation-based WPM with minor revision to solve the extended CSG problem where the value of a coalition is affected by the formation of other coalitions, a coalition known as externality. Experiments demonstrate that, compared to the previous encoding, our proposed method speeds up the process of solving the CSG problem significantly, as it generates fewer number of Boolean variables and clauses that need to be examined by WPM solver.

We design M(≥3)-phase spreading sequences of Markov chains optimal in terms of bit error probabilities in asynchronous SSMA (spread spectrum multiple access) communication systems. To this end, we obtain the distributions of the normalized MAI (multiple access interference) for such systems and find a necessary and sufficient condition that the distributions become independent of the phase shifts.

We consider a problem of the choice of price plans offered by a telecommunications company: a “pay-as-you-go” plan and a “flat-rate” plan. This problem is formulated as an online optimization problem extending the ski-rental problem, and analyzed using the competitive ratio. We give a lemma for easily calculating the competitive ratio. Based on the lemma, we derive a family of optimal strategies for a realistic class of instances.

A laser power optimizing method for multi-pulse recording is described. Multi-pulse recording uses the recording pulse formed by bias part and comb part. To obtain best readout signal characteristics and reduce the time for optimizing, new mark pattern is recorded and then two parts of the recording pulse are individually adjusted by evaluating the detected signals during pre-write testing. At the optimized laser power by this method, a good qualitative eyepattern was obtained. As a result, this new method proves to be suitable for the multi-pulse recording and adapted to various disks with different recording properties.

We study asynchronous SSMA communication systems using binary spreading sequences of Markov chains and prove the CLT (central limit theorem) for the empirical distribution of the normalized MAI (multiple-access interference). We also prove that the distribution of the normalized MAI for asynchronous systems can never be Gaussian if chains are irreducible and aperiodic. Based on these results, we propose novel theoretical evaluations of bit error probabilities in such systems based on the CLT and compare these and conventional theoretical estimations based on the SGA (standard Gaussian approximation) with experimental results. Consequently we confirm that the proposed theoretical evaluations based on the CLT agree with the experimental results better than the theoretical evaluations based on the SGA. Accordingly, using the theoretical evaluations based on the CLT, we give the optimum spreading sequences of Markov chains in terms of bit error probabilities.

Thin films of vinyl derivatives of naphthalene diimide were prepared by electron-assisted vapor deposition. Monomer materials of N, N'-bis(allyl)-naphthalene diimide (Allyl-NDI) and N,N'-bis(p-vinyl-benzyl)-naphthalene diimide (Sty-NDI) were newly synthesized for this purpose. Uniform films were obtained by vapor-depositing these materials, whereas spin-coating yielded nonuniform films. IR analysis suggested that Sty-NDI can be polymerized upon vapor deposition. An insoluble film of Sty-NDI was obtained by the electron-assisted vapor deposition. On the other hand, Allyl-NDI had lower reactivity for polymerization. It was concluded that Sty-NDI is a promising material for preparing thin films of vinyl polymer having naphthalene diimide units.

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.

This paper presents a new method to translate a regular expression into a nondeterministic finite automaton (an NFA for short). Let r be a regular expression and let M be a Thompson automaton for r. We first introduce a labeled Thompson automaton defined by assigning two types of expressions which denote prefixes and suffixes of words in L(r) to each state of M. Then we give new ϵ-free NFAs constructed from a labeled Thompson automaton. These NFAs are called a prefix equation automaton and a suffix equation automaton. We show that a suffix equation automaton is isomorphic to an equation automaton defined by Antimirov. Furthermore we give an NFA called a unified equation automaton by joining two NFAs. Thus the number of states of a unified equation automaton can be smaller than that of an equation automaton.

The multislope ski-rental problem is an online optimization problem that generalizes the classical ski-rental problem. The player is offered not only a buy and a rent options but also other options that charge both initial and per-time fees. The competitive ratio of the classical ski-rental problem is known to be 2. In contrast, the best known so far on the competitive ratio of the multislope ski-rental problem is an upper bound of 4 and a lower bound of 3.62. In this paper we consider a parametric version of the multislope ski-rental problem, regarding the number of options as a parameter. We prove an upper bound for the parametric problem which is strictly less than 4. Moreover, we give a simple recurrence relation that yields an equation having a lower bound value as its root.

A searchable symmetric encryption (SSE) scheme is a method that searches encrypted data without decrypting it. In this paper, we address the substring search problem such that for a set D of documents and a pattern p, we find all occurrences of p in D. Here, a document and a pattern are defined as a string. A directed acyclic word graph (DAWG), which is a deterministic finite automaton, is known for solving a substring search problem on a plaintext. We improve a DAWG so that all transitions of a DAWG have distinct symbols. Besides, we present a space-efficient and secure substring SSE scheme using an improved DAWG. The proposed substring SSE scheme consists of an index with a simple structure, and the size is O(n) for the total size n of documents.

The enlargement of the left lobe of the liver and the shrinkage of the right lobe are helpful signs at MR imaging in diagnosis of cirrhosis of the liver. To investigate whether the volume ratio of left-to-whole (LTW) is effective to differentiate cirrhosis from a normal liver, we developed an automatic algorithm for three-dimensional (3D) segmentation and volume calculation of the liver region in multi-detector row CT scans and MR imaging. From one manually selected slice that contains a large liver area, two edge operators are applied to obtain the initial liver area, from which the mean gray value is calculated as threshold value in order to eliminate the connected organs or tissues. The final contour is re-confirmed by using thresholding technique. The liver region in the next slice is generated by referring to the result from the last slice. After continuous procedure of this segmentation on each slice, the 3D liver is reconstructed from all the extracted slices and the surface image can be displayed from different view points by using the volume rendering technique. The liver is then separated into the left and the right lobe by drawing an inter-segmental plane manually, and the volume in each part is calculated slice by slice. The degree of cirrhosis can be defined as the ratio of volume in these two lobes. Four cases including normal and cirrhotic liver with MR and CT slices are used for 3D segmentation and visualization. The volume ratio of LTW was relatively higher in cirrhosis than in the normal cases in both MR and CT cases. The average error rate on liver segmentation was within 5.6% after employing in 30 MR cases. These results demonstrate that the performance in our 3D segmentation was satisfied and the LTW ratio may be effective to differentiate cirrhosis.

This paper tries to solve open Job-Shop Scheduling Problems (JSSP) by translating them into Boolean Satisfiability Testing Problems (SAT). The encoding method is essentially the same as the one proposed by Crawford and Baker. The open problems are ABZ8, ABZ9, YN1, YN2, YN3, and YN4. We proved that the best known upper bounds 678 of ABZ9 and 884 of YN1 are indeed optimal. We also improved the upper bound of YN2 and lower bounds of ABZ8, YN2, YN3 and YN4.

Common-mode excitation caused by an imperfect ground plane on a printed circuit board (PCB) has been conventionally explained with the 'current driven' scheme, in which the common-mode current is driven by the ground voltage across the unintentional inductance of the ground plane. We have developed an alternative method for estimating common-mode excitation that is driven by the difference of the common-mode voltages for two connected transmission lines. A parameter called current division factor (CDF) that represents the degree of imbalance of a transmission line explains the common-mode voltage. In this paper, we calculate the CDF with two-dimensional (2-D) static electric field analysis by using the boundary element method (BEM) for asymmetric transmission lines with an arbitrary cross-section. The proposed 2-D method requires less time than three-dimensional simulations. The EMI increase due to a signal line being close to the edge of the ground pattern was evaluated through CDF calculation. The estimated increase agreed well--within 2 dB--with the measured one.

This paper presents a combinatiorial characterization of broadcast authentication in which a transmitter broadcasts v messages e1(s), , ev(s) to authenticate a source state s to all n receivers so that any k receivers cannot cheat any other receivers, where ei is a key. Suppose that each receiver has l keys. First, we prove that k < l if v < n. Then we show an upper bound of n such that n v(v - 1)/l(l - 1) for k = l - 1 and n /+ for k < l - 1. Further, a scheme for k = 1 - 1 which meets the upper bound is presented by using a BIBD and a scheme for k < l - 1 such than n = / is presented by using a Steiner system. Some other efficient schemes are also presented.

Our purpose in this study is to develop a scheme to segment the rectus abdominis muscle region in X-ray CT images. We propose a new muscle recognition method based on the shape model. In this method, three steps are included in the segmentation process. The first is to generate a shape model for representing the rectus abdominis muscle. The second is to recognize anatomical feature points corresponding to the origin and insertion of the muscle, and the third is to segment the rectus abdominis muscles using the shape model. We generated the shape model from 20 CT cases and tested the model to recognize the muscle in 10 other CT cases. The average value of the Jaccard similarity coefficient (JSC) between the manually and automatically segmented regions was 0.843. The results suggest the validity of the model-based segmentation for the rectus abdominis muscle.

In the bin packing problem, we are asked to place given items, each being of size between zero and one, into bins of capacity one. The goal is to minimize the number of bins that contain at least one item. An online algorithm for the bin packing problem decides where to place each item one by one when it arrives. The asymptotic approximation ratio of the bin packing problem is defined as the performance of an optimal online algorithm for the problem. That value indicates the intrinsic hardness of the bin packing problem. In this paper we study the bin packing problem in which every item is of either size α or size β (≤ α). While the asymptotic approximation ratio for $alpha > rac{1}{2}$ was already identified, that for $alpha leq rac{1}{2}$ is only partially known. This paper is the first to give a lower bound on the asymptotic approximation ratio for any $alpha leq rac{1}{2}$, by formulating linear optimization problems. Furthermore, we derive another lower bound in a closed form by constructing dual feasible solutions.