Yutaro Yamaguchi

Ryo Suzuki, Yutaro Yamaguchi

In the sliding window model, we are required to maintain the target statistics over the most recent $n$ elements of a data stream, which is captured by a window of size $n$ sliding over the data stream. Exact computation usually requires space linear in $n$, and the central goal is approximate maintenance using sublinear space. In this paper, we study the problem of maintaining the maximum subarray sum in the sliding window model. While the classical Kadane's algorithm computes the exact answer using constant space in the static setting, it does not extend directly, because a new element makes the oldest one expire, which may invalidate the optimal subarray so far. Our first observation is that the so-called Smooth Histogram framework can lead to a constant-factor approximation (in the sense of relative error) using $O((\log n)^2)$ bits of space. We then refine this framework accordingly, which enables for any $ε> 0$ to maintain a $(1 \pm ε)$-approximation using $O(ε^{-1}(\log n)^2)$ bits of space and $O(ε^{-1}\log n)$ operations per update. The space complexity is asymptotically optimal.

Kristóf Bérczi, Viktor Csaplár, Yutaro Yamaguchi

Motivated by the exact weight perfect matching problem and recent parameterized algorithms for finding an $\ell$-th smallest perfect matching, we study structural properties of edge-weight symmetries in graphs. Recent work by El Maalouly et al. (ESA 2025) showed that excluding all perfect matchings whose weight is at most the $(\ell - 1)$-th smallest possible value in the graph requires fixing at most $2(\ell-1)$ edges in non-bipartite graphs and at most $\ell-1$ edges in bipartite graphs. A natural open question is whether fixing a single edge is always sufficient to shift the extreme (minimum or maximum) weight of a perfect matching when the global minimum and maximum weights differ. To address this, we define and analyze a hierarchy of progressively weaker edge-weight properties: node-induced weights, even walk and cycle symmetries, perfect matching equality, and the edge min-max property. We derive a basic hierarchy among these conditions and show that they become equivalent in bipartite graphs. For general graphs, we provide tight structural characterizations, based on block and tight cut decompositions, under which even cycle symmetry and perfect matching equality force node-induced weights. Finally, we resolve the motivating open question in the negative by constructing a matching-covered non-bipartite graph that satisfies the edge min-max property (every edge is contained in a minimum-weight perfect matching and a maximum-weight one) but violates perfect matching equality (all perfect matchings have the same weight). This counterexample shows that a single edge is not always sufficient to eliminate all minimum-weight or maximum-weight perfect matchings, thereby proving the tightness of the $2(\ell-1)$ bound for $\ell=2$. We also discuss extensions of this framework to $b$-factors and arborescences.

Daisuke Shibatani, Yutaro Yamaguchi

We study an application of fair division theory to school redistricting. Procaccia, Robinson, and Tucker-Foltz (SODA 2024) recently proposed a mathematical model to generate redistricting plans that provide theoretically guaranteed fairness among demographic groups of students. They showed that an almost proportional allocation can be found by adding $O(g \log g)$ extra seats in total, where $g$ is the number of groups. In contrast, for three or more groups, adding $o(n)$ extra seats is not sufficient to obtain an almost envy-free allocation in general, where $n$ is the total number of students. In this paper, we focus on the case of two groups. We introduce a relevant relaxation of envy-freeness, termed 1-relaxed envy-freeness, which limits the capacity violation not in total but at each school to at most one. We show that there always exists a 1-relaxed envy-free allocation, which can be found in polynomial time.

Shinnosuke Uba, Yutaro Yamaguchi

The Competing Bandits framework is a recently emerging area that integrates multi-armed bandits in online learning with stable matching in game theory. While conventional models assume that all players and arms are constantly available, in real-world problems, their availability can vary arbitrarily over time. In this paper, we formulate this setting as Sleeping Competing Bandits. To analyze this problem, we naturally extend the regret definition used in existing competing bandits and derive regret bounds for the proposed model. We propose an algorithm that simultaneously achieves an asymptotic regret bound of $\mathrm{O}\left(NK\log T_{i}/Δ^2\right)$ under reasonable assumptions, where $N$ is the number of players, $K$ is the number of arms, $T_{i}$ is the number of rounds of each player $p_i$, and $Δ$ is the minimum reward gap. We also provide a regret lower bound of $\mathrmΩ\left( N(K-N+1)\log T_{i}/Δ^2 \right)$ under the same assumptions. This implies that our algorithm is asymptotically optimal in the regime where the number of arms $K$ is relatively larger than the number of players $N$.

Takumi Kano, Yutaro Yamaguchi

We present a deterministic linear-time algorithm for finding an odd cycle through two specified vertices in an undirected graph. This is shown in a generalized form as follows: Let $Γ$ be any group in which every element is of order at most $2$. For a given $Γ$-labeled graph with two specified vertices (or edges), we can determine in linear time whether there exist two cycles with distinct labels that are through both of the two specified vertices (or edges), and find such cycles if yes.

Yoshinobu Kawahara, Yutaro Yamaguchi

The proximal problem for structured penalties obtained via convex relaxations of submodular functions is known to be equivalent to minimizing separable convex functions over the corresponding submodular polyhedra. In this paper, we reveal a comprehensive class of structured penalties for which penalties this problem can be solved via an efficiently solvable class of parametric maxflow optimization. We then show that the parametric maxflow algorithm proposed by Gallo et al. and its variants, which runs, in the worst-case, at the cost of only a constant factor of a single computation of the corresponding maxflow optimization, can be adapted to solve the proximal problems for those penalties. Several existing structured penalties satisfy these conditions; thus, regularized learning with these penalties is solvable quickly using the parametric maxflow algorithm. We also investigate the empirical runtime performance of the proposed framework.