22 citations · 63 across the 20 of their papers we have counts for
10 papers · 1 filter
-Approximation Algorithms for Bipartiteness Ratio
Tasuku Soma, Mingquan Ye, Yuichi Yoshida
We propose an -approximation algorithm for the bipartiteness ratio of undirected graphs introduced by Trevisan (SIAM Journal on Computing, vol. 41, no. 6, 2012), where $…
Online Algorithms for Spectral Hypergraph Sparsification
Tasuku Soma, Kam Chuen Tung, Yuichi Yoshida
We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival…
Shrunk subspaces via operator Sinkhorn iteration
Cole Franks, Tasuku Soma, Michel X. Goemans
A recent breakthrough in Edmonds' problem showed that the noncommutative rank can be computed in deterministic polynomial time, and various algorithms for it were devised. However,…
Online Risk-Averse Submodular Maximization
Tasuku Soma, Yuichi Yoshida
We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given i.i.d. samples from an und…
Spectral Sparsification of Hypergraphs
Tasuku Soma, Yuichi Yoshida
For an undirected/directed hypergraph , its Laplacian is defined such that its ``quadratic form'' $\boldsymbol{x}^\top L_G(\boldsym…
No-regret algorithms for online -submodular maximization
Tasuku Soma
We present a polynomial time algorithm for online maximization of -submodular maximization. For online (nonmonotone) -submodular maximization, our algorithm achieves a tight…
Polynomial-Time Algorithms for Submodular Laplacian Systems
Kaito Fujii, Tasuku Soma, Yuichi Yoshida
Let be an undirected graph, be the associated Laplacian matrix, and be a vector. Solving the Laplacian system $L_G x…
A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity
Tasuku Soma, Yuichi Yoshida
In monotone submodular function maximization, approximation guarantees based on the curvature of the objective function have been extensively studied in the literature. However, th…
Non-monotone DR-Submodular Function Maximization
Tasuku Soma, Yuichi Yoshida
We consider non-monotone DR-submodular function maximization, where DR-submodularity (diminishing return submodularity) is an extension of submodularity for functions over the inte…
Maximizing Monotone Submodular Functions over the Integer Lattice
Tasuku Soma, Yuichi Yoshida
The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the probl…