6 citations · 21 across the 12 of their papers we have counts for
9 papers · 1 filter
Online Task Assignment Problems with Reusable Resources
Hanna Sumita, Shinji Ito, Kei Takemura +4
We study online task assignment problem with reusable resources, motivated by practical applications such as ridesharing, crowdsourcing and job hiring. In the problem, we are given…
Adaptive Algorithm for Finding Connected Dominating Sets in Uncertain Graphs
Takuro Fukunaga
The problem of finding a minimum-weight connected dominating set (CDS) of a given undirected graph has been studied actively, motivated by operations of wireless ad hoc networks. I…
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…
Computing a tree having a small vertex cover
Takuro Fukunaga, Takanori Maehara
We consider a new Steiner tree problem, called vertex-cover-weighted Steiner tree problem. This problem defines the weight of a Steiner tree as the minimum weight of vertex covers…
Constant-approximation algorithms for highly connected multi-dominating sets in unit disk graphs
Takuro Fukunaga
Given an undirected graph on a node set and positive integers and , a -connected -dominating set (-CDS) is defined as a subset of such that each nod…
Approximating the generalized terminal backup problem via half-integral multiflow relaxation
Takuro Fukunaga
We consider a network design problem called the generalized terminal backup problem. Whereas earlier work investigated the edge-connectivity constraints only, we consider both edge…
Covering problems in edge- and node-weighted graphs
Takuro Fukunaga
This paper discusses the graph covering problem in which a set of edges in an edge- and node-weighted graph is chosen to satisfy some covering constraints while minimizing the sum…
Spider covers for prize-collecting network activation problem
Takuro Fukunaga
In the network activation problem, each edge in a graph is associated with an activation function, that decides whether the edge is activated from node-weights assigned to its end-…
Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
Takuro Fukunaga, Zeev Nutov, R. Ravi
We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iter…