Source author record

Yasushi Kawase

Yasushi Kawase appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Computer Science and Game Theory Machine Learning physics.soc-ph Social and Information Networks

Catalog footprint

What is connected

5works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio

The field of algorithms with predictions aims to improve algorithm performance by integrating machine learning predictions into algorithm design. A central question in this area is how predictions can improve performance, and a key aspect of this analysis is the role of prediction accuracy. In this context, prediction accuracy is defined as a guaranteed probability that an instance drawn from the distribution belongs to the predicted set. As a performance measure that incorporates prediction accuracy, we focus on the distributionally-robust competitive ratio (DRCR), introduced by Sun et al.~(ICML 2024). The DRCR is defined as the expected ratio between the algorithm's cost and the optimal cost, where the expectation is taken over the worst-case instance distribution that satisfies the given prediction and accuracy requirement. A known structural property is that, for any fixed algorithm, the DRCR decreases linearly as prediction accuracy increases. Building on this result, we establish that the optimal DRCR value (i.e., the infimum over all algorithms) is a monotone and concave function of prediction accuracy. We further generalize the DRCR framework to a multiple-prediction setting and show that monotonicity and concavity are preserved in this setting. Finally, we apply our results to the ski rental problem, a benchmark problem in online optimization, to identify the conditions on prediction accuracies required for the optimal DRCR to attain a target value. Moreover, we provide a method for computing the critical accuracy, defined as the minimum accuracy required for the optimal DRCR to strictly improve upon the performance attainable without any accuracy guarantee.

preprint2020arXiv

Tight Approximation for Unconstrained XOS Maximization

A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width $1$ because they are just additive, but it is already nontrivial even when the width is restricted to $2$. We show two types of tight bounds on the polynomial-time approximability for this problem. First, in general, the approximation bound is between $O(n)$ and $Ω(n / \log n)$, and exactly $Θ(n / \log n)$ if randomization is allowed, where $n$ is the ground set size. Second, when the width of the input XOS functions is bounded by a constant $k \geq 2$, the approximation bound is between $k - 1$ and $k - 1 - ε$ for any $ε> 0$. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width $2$, while we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to $3$.

preprint2016arXiv

Optimal Composition Ordering Problems for Piecewise Linear Functions

In this paper, we introduce maximum composition ordering problems. The input is $n$ real functions $f_1,\dots,f_n:\mathbb{R}\to\mathbb{R}$ and a constant $c\in\mathbb{R}$. We consider two settings: total and partial compositions. The maximum total composition ordering problem is to compute a permutation $σ:[n]\to[n]$ which maximizes $f_{σ(n)}\circ f_{σ(n-1)}\circ\dots\circ f_{σ(1)}(c)$, where $[n]=\{1,\dots,n\}$. The maximum partial composition ordering problem is to compute a permutation $σ:[n]\to[n]$ and a nonnegative integer $k~(0\le k\le n)$ which maximize $f_{σ(k)}\circ f_{σ(k-1)}\circ\dots\circ f_{σ(1)}(c)$. We propose $O(n\log n)$ time algorithms for the maximum total and partial composition ordering problems for monotone linear functions $f_i$, which generalize linear deterioration and shortening models for the time-dependent scheduling problem. We also show that the maximum partial composition ordering problem can be solved in polynomial time if $f_i$ is of form $\max\{a_ix+b_i,c_i\}$ for some constants $a_i\,(\ge 0)$, $b_i$ and $c_i$. We finally prove that there exists no constant-factor approximation algorithm for the problems, even if $f_i$'s are monotone, piecewise linear functions with at most two pieces, unless P=NP.

preprint2016arXiv

Optimal Pricing for Submodular Valuations with Bounded Curvature

The optimal pricing problem is a fundamental problem that arises in combinatorial auctions. Suppose that there is one seller who has indivisible items and multiple buyers who want to purchase a combination of the items. The seller wants to sell his items for the highest possible prices, and each buyer wants to maximize his utility (i.e., valuation minus payment) as long as his payment does not exceed his budget. The optimal pricing problem seeks a price of each item and an assignment of items to buyers such that every buyer achieves the maximum utility under the prices. The goal of the problem is to maximize the total payment from buyers. In this paper, we consider the case that the valuations are submodular. We show that the problem is computationally hard even if there exists only one buyer. Then we propose approximation algorithms for the unlimited budget case. We also extend the algorithm for the limited budget case when there exists one buyer and multiple buyers collaborate with each other.

preprint2015arXiv

Z-score-based modularity for community detection in networks

Identifying community structure in networks is an issue of particular interest in network science. The modularity introduced by Newman and Girvan [Phys. Rev. E 69, 026113 (2004)] is the most popular quality function for community detection in networks. In this study, we identify a problem in the concept of modularity and suggest a solution to overcome this problem. Specifically, we obtain a new quality function for community detection. We refer to the function as Z-modularity because it measures the Z-score of a given division with respect to the fraction of the number of edges within communities. Our theoretical analysis shows that Z-modularity mitigates the resolution limit of the original modularity in certain cases. Computational experiments using both artificial networks and well-known real-world networks demonstrate the validity and reliability of the proposed quality function.