3 papers
cs.DS2021
A 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion
Susumu Hashimoto, Shinji Mizuno
This paper studies a single-machine scheduling problem with a non-renewable resource (NR-SSP) and total weighted completion time criterion. The non-renewable resource is consumed w…
cs.DM2018
On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem
Yotaro Takazawa, Shinji Mizuno
We study the weighted induced bipartite subgraph problem (WIBSP). The goal of WIBSP is, given a graph and nonnegative weights for the nodes, to find a set W of nodes with the maxim…
math.OC2016
A simple proof of tail--polynomial bounds on the diameter of polyhedra
Shinji Mizuno, Noriyoshi Sukegawa
Let denote the maximum diameter of a -dimensional polyhedron with facets. In this paper, we propose a unified analysis of a recursive inequality about esta…