This paper introduces a novel framework for survival analysis by reinterpreting it as a form of density estimation. Our algorithm post-processes density estimation outputs to derive survival functions, enabling the application of any density estimation model to effectively estimate survival functions. This approach broadens the toolkit for survival analysis and enhances the flexibility and applicability of existing techniques. Our framework is versatile enough to handle various survival analysis scenarios, including competing risk models for multiple event types. It can also address dependent censoring when prior knowledge of the dependency between event time and censoring time is available in the form of a copula. In the absence of such information, our framework can estimate the upper and lower bounds of survival functions, accounting for the associated uncertainty.

Survival analysis is the problem of estimating probability distributions for future event times, which can be seen as a problem in uncertainty quantification. Although there are fundamental theories on strictly proper scoring rules for uncertainty quantification, little is known about those for survival analysis. In this paper, we investigate extensions of four major strictly proper scoring rules for survival analysis and we prove that these extensions are proper under certain conditions, which arise from the discretization of the estimation of probability distributions. We also compare the estimation performances of these extended scoring rules by using real datasets, and the extensions of the logarithmic score and the Brier score performed the best.

Partially monotone regression is a regression analysis in which the target values are monotonically increasing with respect to a subset of input features. The TensorFlow Lattice library is one of the standard machine learning libraries for partially monotone regression. It consists of several neural network layers, and its core component is the lattice layer. One of the problems of the lattice layer is that it requires the projected gradient descent algorithm with many constraints to train it. Another problem is that it cannot receive a high-dimensional input vector due to the memory consumption. We propose a novel neural network layer, the hierarchical lattice layer (HLL), as an extension of the lattice layer so that we can use a standard stochastic gradient descent algorithm to train HLL while satisfying monotonicity constraints and so that it can receive a high-dimensional input vector. Our experiments demonstrate that HLL did not sacrifice its prediction performance on real datasets compared with the lattice layer.

In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the well-known stable mechanisms is the man-oriented Gale-Shapley algorithm (MGS). MGS has a good property that it is strategy-proof to the men’s side, i.e., no man can obtain a better outcome by falsifying a preference list. We call such a mechanism a man-strategy-proof mechanism. Unfortunately, MGS is not a woman-strategy-proof mechanism. (Of course, if we flip the roles of men and women, we can see that the woman-oriented Gale-Shapley algorithm (WGS) is a woman-strategy-proof but not a man-strategy-proof mechanism.) Roth has shown that there is no stable mechanism that is simultaneously man-strategy-proof and woman-strategy-proof, which is known as Roth’s impossibility theorem. In this paper, we extend these results to the stable marriage problem with ties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth’s impossibility theorem takes over to SMTI. Therefore, we focus on the one-sided-strategy-proofness. In SMTI, one instance can have stable matchings of different sizes, and it is natural to consider the problem of finding a largest stable matching, known as MAX SMTI. Thus we incorporate the notion of approximation ratios used in the theory of approximation algorithms. We say that a stable-mechanism is a c-approximate-stable mechanism if it always returns a stable matching of size at least 1/c of a largest one. We also consider a restricted variant of MAX SMTI, which we call MAX SMTI-1TM, where only men’s lists can contain ties (and women’s lists must be strictly ordered). Our results are summarized as follows: (i) MAX SMTI admits both a man-strategy-proof 2-approximate-stable mechanism and a woman-strategy-proof 2-approximate-stable mechanism. (ii) MAX SMTI-1TM admits a woman-strategy-proof 2-approximate-stable mechanism. (iii) MAX SMTI-1TM admits a man-strategy-proof 1.5-approximate-stable mechanism. All these results are tight in terms of approximation ratios. Also, all these results apply for strategy-proofness against coalitions.

Detecting the densest subgraph is one of the most important problems in graph mining and has a variety of applications. Although there are many possible metrics for subgraph density, there is no consensus on which density metric we should use. In this article, we suggest a new density metric, the discounted average degree, which has some desirable properties of the subgraph's density. We also show how to obtain an optimum densest subgraph for small graphs with respect to several density metrics, including our new density metric, by using mixed integer programming. Finally, we develop a new heuristic algorithm to quickly obtain a good approximate solution for large graphs. Our computational experiments on real‐world graphs showed that our new heuristic algorithm outperformed other heuristics in terms of the quality of the solutions. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(1), 3–15 2018

Two-sample feature selection is a ubiquitous problem in both scientific and engineering studies. We propose a feature selection method to find features that describe a difference in two probability distributions. The proposed method is nonparametric and does not assume any specific parametric models on data distributions. We show that the proposed method is computationally efficient and does not require any extra computation for model selection. Moreover, we prove that the proposed method provides a consistent estimator of features under mild conditions. Our experimental results show that the proposed method outperforms the current method with regard to both accuracy and computation time.

The anomaly localization task aims at detecting faulty sensors automatically by monitoring the sensor values. In this paper, we propose an anomaly localization algorithm with a consistency guarantee on its results. Although several algorithms were proposed in the last decade, the consistency of the localization results was not discussed in the literature. To the best of our knowledge, this is the first study that provides theoretical guarantees for the localization results. Our new approach is to formulate the task as solving the sparsest subgraph problem on a difference graph. Since this problem is NP-hard, we then use a convex quadratic programming approximation algorithm, which is guaranteed to be consistent under suitable conditions. Across the simulations on both synthetic and real world datasets, we verify that the proposed method achieves higher anomaly localization performance compared to existing methods.

The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear only in women's preference lists and (ii) each tie appears at the end of each woman's preference list. The current best lower bounds on the approximation ratio for this variant are 1.1052 unless P=NP and 1.25 under the unique games conjecture, while the current best upper bound is 1.4616. In this paper, we improve the upper bound to 1.25, which matches the lower bound under the unique games conjecture. Note that this is the first special case of the MAX SMTI where the tight approximation bound is obtained. The improved ratio is achieved via a new analysis technique, which avoids the complicated case-by-case analysis used in earlier studies. As a by-product of our analysis, we show that the integrality gap of natural IP and LP formulations for this variant is 1.25. We also show that the unrestricted MAX SMTI cannot be approximated with less than 1.5 unless the approximation ratio of a certain special case of the minimum maximal matching problem can be improved.

Reducing the energy used in Cloud Computing is an important issue a sustainable society. There are many existing approaches for reducing energy use in data centers, but new approaches are needed in case of energy management of Cloud Computing. Cloud Computing involves decentralized data centers, so new flexible way for collecting energy consumption data becomes quite important. Many current approaches focus on reducing energy consumption by air handling equipment, however energy from IT resources also need to be optimized for a total energy management of Cloud Computing. For advanced energy management for Cloud Computing, we developed a Cloud energy management system with sensor management functions, with an optimized VM allocation tool to minimize energy consumption at multiple data centers. Our evaluations showed more than a 30% energy savings for the servers in our experimental environment. Our system can be extended to optimize energy usage from various perspectives, such as for minimizing electricity bills or carbon emissions.

The difficulty in allocating virtual machines (VMs) on servers stems from the requirement that sufficient resources (such as CPU capacity and network bandwidth) must be available for each VM in the event of a failure or maintenance work as well as for temporal fluctuations of resource demands, which often exhibit periodic patterns. We propose a mixed integer programming approach that considers the fluctuations of the resource demands for optimal and dependable allocation of VMs. At the heart of the approach are techniques for optimally partitioning the time-horizon into intervals of variable lengths and for reliably estimating the resource demands in each interval. We show that our new approach allocates VMs successfully in a cloud computing environment in a financial company, where the dependability requirement is strict and there are various types of VMs exist.

There is a long history of developing efficient algorithms for set intersection, which is a fundamental operation in information retrieval and databases. In this paper, we describe a new data structure, a Cardinality Filter, to quickly compute an upper bound on the size of a set intersection. Knowing an upper bound of the size can be used to accelerate many applications such as top-k query processing in text mining. Given finite sets A and B, the expected computation time for the upper bound of the size of the intersection |A cap B| is O( (|A| + |B|) w), where w is the machine word length. This is much faster than the current best algorithm for the exact intersection, which runs in O((|A| + |B|) / √w + |A cap B|) expected time. Our performance studies show that our implementations of Cardinality Filters are from 2 to 10 times faster than existing set intersection algorithms, and the time for a top-k query in a text mining application can be reduced by half.

The map matching problem is, given a spatial road network and a sequence of locations of an object moving on the network, to identify the path in the network that the moving object passed through. In this paper, an integer programming formulation for the offline map matching problem is presented. This is the first approach that gives the optimal solution with respect to a widely used objective function for map matching.

The All-Pairs Shortest Paths (APSP) problem seeks the shortest path distances between all pairs of vertices, and is one of the most fundamental graph problems. In this paper, a fast algorithm with a small working space for the APSP problem on sparse graphs is presented, which first divides the vertices into sets of vertices with each set having a constant number of vertices and then solves the multi-source shortest paths (MSSP) problem for each set in parallel. For solving the MSSP problems, we give a multi-source label-correcting algorithm, as an extension of a label-correcting algorithm for the single-source shortest path problem. Our algorithm uses fewer operations on the priority queue than an implementation based on Dijkstra's algorithm. Our experiments showed that an implementation of our algorithm with SIMD instructions achieves an order of magnitude speedup for real-world geometric graphs compared to an implementation based on Dijkstra's algorithm.

The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this algorithm is man-optimal, that is, the matching is favorable for men but unfavorable for women, (or, if we exchange the roles of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem, posed by Gusfield and Irving, seeks a stable matching “fair” for both genders. Specifically it seeks a stable matching with the property that the sum of the men's scores is as close as possible to that of the women's. This problem is known to be strongly NP-hard. In this paper, we give a polynomial time algorithm for finding a near optimal solution for the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing an additional criterion: among stable matchings that are near optimal in terms of the sex-equality, find a minimum egalitarian stable matching. We show that this problem is strongly NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two.

The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2/(1 + L −2 ) for instances in which only men have ties of length at most L . When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13/7(<1.858). We also improve the lower bound on the approximation ratio to 21/19(>1.1052).