93 citations · 202 across the 25 of their papers we have counts for
8 papers · 1 filter
Online Knapsack Problems with a Resource Buffer
Xin Han, Yasushi Kawase, Kazuhisa Makino +1
In this paper, we introduce online knapsack problems with a resource buffer. In the problems, we are given a knapsack with capacity , a buffer with capacity , and items…
Tight Approximation for Unconstrained XOS Maximization
Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi +1
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…
Randomized Strategies for Robust Combinatorial Optimization
Yasushi Kawase, Hanna Sumita
In this paper, we study the following robust optimization problem. Given an independence system and candidate objective functions, we choose an independent set, and then an adversa…
Submodular maximization with uncertain knapsack capacity
Yasushi Kawase, Hanna Sumita, Takuro Fukunaga
We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint. Specifically, the problem is discussed in the situation that the knaps…
Optimal Matroid Partitioning Problems
Yasushi Kawase, Kei Kimura, Kazuhisa Makino +1
This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set and weighted matroids $(E, \mathcal{I}_i…
Stochastic Input Models in Online Computing
Yasushi Kawase
In this paper, we study twelve stochastic input models for online problems and reveal the relationships among the competitive ratios for the models. The competitive ratio is define…
The Densest Subgraph Problem with a Convex/Concave Size Function
Yasushi Kawase, Atsushi Miyauchi
In the densest subgraph problem, given an edge-weighted undirected graph , we are asked to find that maximizes the density, i.e., , where …
Optimal Composition Ordering Problems for Piecewise Linear Functions
Yasushi Kawase, Kazuhisa Makino, Kento Seimi
In this paper, we introduce maximum composition ordering problems. The input is real functions and a constant . We consi…