Publications

MI Preprints



2016-15
Title:A Note on Submodular Function Minimization with Covering Type Linear Constraints
Author : Naoyuki Kamiyama
Abstract: In this paper, we propose a primal-dual approximation algorithm for the submodular function minimization problem with covering type linear constraints. Our algorithm is based on the approximation algorithm of Takazawa and Mizuno for the covering integer program with {0,1}-variables, and the approximation algorithm of Iwata and Nagano for the submodular function minimization problem with a set covering constraint.

File: 2016-15pdf

2016-14
Title:An Algorithm for the Evacuation Problem based on Parametric Submodular Function Minimization
Author : Naoyuki Kamiyama
Abstract: A dynamic network is a directed graph in which arcs have capacities and transit times. In this paper, we consider the evacuation problem in a dynamic network. In this problem, we are given a dynamic network with a single sink vertex in which each vertex except the sink vertex has a supply. Then, the goal of this problem is to find a minimum time limit T such that we can send all supplies to the sink vertex within T. It is known that this problem can be solved in polynomial time by using a submodular function minimization algorithm as a subroutine. However, in practical applications, an algorithm based on a time-expanded network are frequently used instead of a submodular function minimization algorithm be- cause an algorithm based on a time-expanded network can be easily implemented. The aim of this paper is to propose a practically faster algorithm for the evacuation problem based on time-expanded networks. More precisely, we first propose a theoretical algorithm for the evacuation problem by using a parametric submodular function minimization algorithm, and then we give a practical algorithm based on this theoretical algorithm.

File: 2016-14pdf

2016-13
Title:Popular Matchings with Two-Sided Preference Lists and Matroid Constraints
Author : Naoyuki Kamiyama
Abstract: In this paper, we first propose the popular matching problem with two-sided preference lists and matroid constraints based on the many-to-one variants of the popular matching problem proposed by Brandl and Kavitha, and Nasre and Rawat. Then, we prove that there always exists a popular matching in our model. Lastly, we prove that if every matroid is weakly base orderable, then we can find a maximum-size popular matching in polynomial time.

File: 2016-13pdf

2016-12
Title:Large time behavior of the solutions around spatially periodic solution to the compressible Navier-Stokes equation
Author : Shota Enomoto
Abstract: This paper shows that the strong solution to the compressible Navier-Stokes equation around spatially periodic stationary solution in a periodic layer of $\mathbb{R}^n$ $(n=2,3)$ exists globally in time if Reynolds and Mach numbers are sufficiently small. It is proved that the asymptotic leading part of the perturbation is given by a solution to the one-dimensional viscous Burgers equation multiplied by a spatially periodic function when $n=2$, and by a solution to the two-dimensional heat equation multiplied by the spatially periodic function when $n=3$.

File: 2016-12pdf

2016-11
Title:An indirect search algorithm for disaster restoration with precedence and synchronization constraints
Author : Akifumi Kira, Hidenao Iwane, Hirokazu Anai, Yutaka Kimura & Katsuki Fujisawa
Abstract: When a massive disaster occurs, to repair the damaged part of lifeline networks, planning is needed to appropriately allocate tasks to two or more restoration teams and optimize their traveling routes. However, precedence and synchronization constraints make restoration teams interdependent of one another, and impede a successful solution by standard local search. In this paper, we propose an indirect local search method using the product set of team-wise permutations as an auxiliary search space. It is shown that our method successfully avoids the interdependence problem induced by the precedence and synchronization constraints, and that it has the big advantage of non-deteriorating perturbations being available for iterated local search.

File: 2016-11pdf

2016-10
Title:Coalition Structure Generation with Subadditivity Constraints
Author : Naoyuki Kamiyama, Akifumi Kira, Hirokazu Anai, Hidenao Iwane & Kotaro Ohori
Abstract: Coalition structure generation is one of the most fundamental problems in the study of computational aspects of cooperative games. The goal of this problem is to partition the ground set of a given cooperative game in such a way that a certain property is satisfied. For example, one of typical goals is to find a partition that minimizes the sum of costs of all coalitions. In this paper, we introduce the problem of finding a minimum-size partition of the ground set such that a subgame on each coalition is subadditive. The contribution of this paper is twofold. In the first part of this paper, we consider this problem from the theoretical viewpoint. In this part, we prove that our problem in the minimum base game on matroids introduced by Nagamochi, Zeng, Kabutoya, and Ibaraki can be solved in polynomial time. In the second part, we study our problem from the practical viewpoint. In this part, we first propose heuristic algorithms for our problem in a general cooperative game. Our algorithms are based on heuristic algorithms for the set cover problem. Then, we apply our algorithms to the problem of sharing taxis that is our original motivation. More precisely, we consider the problem of partitioning customers for taxis in such a way that customers in each group have incentive for sharing a taxi.

File: 2016-10pdf

2016-9
Title:Gas entrainment rate coefficient of an ideal momentum atomizing liquid jet
Author : Franco Medrano Fermín, Fukumoto Yasuhide, Velte Clara Marika & Hodžić Azur
Abstract: We propose a two-phase-fluid model for a turbulent full-cone highspeed atomizing liquid jet that describes its dynamics in a simple but comprehensive manner with only the apex angle of the cone being a disposable parameter. The basic assumptions are that (i) the jet is statistically stationary and that (ii) it can be approximated by a mixture of a liquid and a gas with its phases in dynamic equilibrium. To derive the model, we impose conservation of the liquid volume and total momentum fluxes. Our model equation admits analytical solutions for the composite density and velocity of the two-phase fluid, both as functions of the distance from the nozzle, from which the dynamic pressure and gas the entrainment rate coefficient are calculated. Assuming a far-field approximation, we theoretically derive a constant gas entrainment rate coefficient solely in terms of the cone angle. Moreover, we carry out experiments for a single-phase turbulent air jet and show that the predictions of our model compare well with this and other experimental data.

File: 2016-9pdf

2016-8
Title:Large time behavior of solutions to the compressible Navier-Stokes equations in an infinite layer under slip boundary condition
Author : Abulizi Aihaiti, Shota Enomoto & Yoshiyuki Kagei
Abstract: This paper is concerned with large time behavior of solutions to the compressible Navier-Stokes equations in an infinite layer of $\mathbb{R}^{2}$ under slip boundary condition. It is shown that if the initial data is sufficiently small, the global solution uniquely exists and the large time behavior of the solution is described by a superposition of one-dimensional diffusion waves.

File: 2016-8pdf

2016-7
Title:Time periodic problem for the compressible Navier-Stokes equation on $R^2$ with antisymmetry
Author : Kazuyuki Tsuda
Abstract: The compressible Navier-Stokes equation is considered on the two dimensional whole space when the external force is periodic in the time variable. The existence of a time periodic solution is proved for sufficiently small time periodic external force with antisymmetry condition. The proof is based on using the time-T-map associated with the linearized problem around the motionless state with constant density. In some weighted $L^\infty$ and Sobolev spaces the spectral properties of the time-T-map is investigated by a potential theoretic method and an energy method. The existence of a stationary solution to the stationary problem is also shown for sufficiently small time-independent external force with antisymmetry condition on $R^2$.

File: 2016-7pdf

2016-6(Published)
Title:Boundary modeling in model-based calibration for automotive engines via the vertex representation of the convex hulls
Author : Hayato Waki & Florin Nae
Abstract: When using the convex hull approach in the boundary modeling process, Model-Based Calibration (MBC) software suites -- such as Model-Based Calibration Toolbox from MathWorks -- can be computationally intensive depending on the amount of data modeled. The reason for this is that the half-space representation of the convex hull is used. We discuss here another representation of the convex hull, the vertex representation, which proves capable to reduce the computational cost. Numerical comparisons in this article are executed in MATLAB by using MBC Toolbox commands, and show that for certain conditions, the vertex representation outperforms the half-space representation.

(Published) Pacific Journal of Mathematics for Industry, vol. 9
http://dx.doi.org/10.1186/s40736-016-0027-7

2016-5
Title:On Chorin's method for stationary solutions of the Oberbeck-Boussinesq equation
Author : Yoshiyuki Kagei & Takaaki Nishida
Abstract: Stability of stationary solutions of the Oberbeck-Boussinesq system (OB) and the corresponding artificial compressible system is considered. The latter system is obtained by adding the time derivative of the pressure with small parameter $\ep>0$ to the continuity equation of (OB), which was proposed by A. Chorin to find stationary solutions of (OB) numerically. Both systems have the same sets of stationary solutions and the system (OB) is obtained from the artificial compressible one as the limit $\ep \to 0$ which is a singular limit. It is proved that if a stationary solution of the artificial compressible system is stable for sufficiently small $\ep>0$, then it is also stable as a solution of (OB). The converse is proved provided that the velocity field of the stationary solution satisfies some smallness condition.

File: 2016-5pdf

2016-4
Title:Non-Gaussian quasi-likelihood estimation of locally stable SDE
Author : Hiroki Masuda
Abstract: We address parametric estimation of both trend and scale coefficients of a pure-jump Levy driven univariate stochastic differential equation (SDE) model based on high-frequency data over a fixed time period. The conventional Gaussian quasi-maximum likelihood estimator is known to be inconsistent. In this paper, under the assumption that the driving Levy process is locally stable, we propose a novel quasi-likelihood function based on the small-time non-Gaussian stable approximation of the unknown transition density. The resulting estimator is shown to be asymptotically mixed-normally distributed and remarkably more efficient than the Gaussian quasi-maximum likelihood estimator. We need neither ergodicity nor existence of finite moments. Compared with the existing methods for estimating SDE models, the proposed quasi-likelihood enables us to achieve better performance in a unified manner for a wide range of the driving Levy processes.

File: 2016-4pdf

2016-3
Title:Asymptotic behavior of the linearized semigroup at space-periodic stationary solution of the compressible Navier-Stokes equation
Author : Shota Enomoto & Yoshiyuki Kagei
Abstract: The asymptotic behavior of the linearized semigroup at spatially periodic stationary solution of the compressible Navier-Stokes equation in a periodic layer of $\mathbb{R}^n$ $(n=2,3)$ is investigated. It is shown that if the Reynolds and Mach numbers are sufficiently small, then the linearized semigroup is decomposed into two parts; one behaves like a solution of an $n-1$ dimensional linear heat equation as time goes to infinity and the other one decays exponentially.

File: 2016-3pdf

2016-2
Title:Asymptotic profiles for the compressible Navier-Stokes equations on the whole space
Author : Yoshiyuki Kagei & Masatoshi Okita
Abstract: This paper is concerned with large time behavior of the strong solutions of the compressible Navier-Stokes equation in the whole space around the motionless state. It was shown by Kawashima-Matsumura-Nishida (1979) and Hoff-Zumbrun (1995) that the perturbation of the motionless state is time-asymptotic to the solution of the linearized problem. In this paper we will give the second-order asymptotics of strong solutions.

File: 2016-2pdf

2016-1(Published)
Title:Analysis of an algorithm to compute the cohomology groups of coherent sheaves and its applications
Author : Momonari Kudo
Abstract: In algebraic geometry, a number of invariants for classifying algebraic varieties are obtained from the cohomology groups of coherent sheaves. Some typical algorithms to compute the dimensions of the cohomology groups have been proposed by Decker and Eisenbud, and their algorithms have been implemented over compute algebra systems such as Macaulay2 and Magma. On the other hand, M. Maruyama showed an alternative method to compute the dimensions in his textbook. However, Maruyama's method was not described in an algorithmic format, and it has not been implemented yet. In this paper, we give an explicit algorithm of his method to compute the dimensions and bases of the cohomology groups of coherent sheaves. We also analyze the complexity of our algorithm, and implemented it over Magma. By our implementation, we examine the computational practicality of our algorithm. Moreover, we give some possible applications of our algorithm in algebraic geometry over fields of positive characteristics.

Japan Journal of Industrial and Applied Mathematics (2017) , pp.1-41
DOI: :10.1007/s13160-017-0238-z
http://link.springer.com/article/10.1007/s13160-017-0238-z