4 citations · 12 across the 21 of their papers we have counts for
14 papers · 1 filter
Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model
Ryo Suzuki, Yutaro Yamaguchi
In the sliding window model, we are required to maintain the target statistics over the most recent elements of a data stream, which is captured by a window of size sliding…
Finding Spanning Trees with Perfect Matchings
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi +2
We investigate the tractability of a simple fusion of two fundamental structures on graphs, a spanning tree and a perfect matching. Specifically, we consider the following problem:…
Matroid Intersection under Minimum Rank Oracle
Mihály Bárász, Kristóf Bérczi, Tamás Király +3
In this paper, we consider the tractability of the matroid intersection problem under the minimum rank oracle. In this model, we are given an oracle that takes as its input a set o…
Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions
Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena +3
We consider the Shortest Odd Path problem, where given an undirected graph , a weight function on its edges, and two vertices and in , the aim is to find an -p…
Matroid Intersection under Restricted Oracles
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds' fundamental theorem provides…
Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application
Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi +1
We consider a dynamic situation in the weighted bipartite matching problem: edge weights in the input graph are repeatedly updated and we are asked to maintain an optimal matching…
Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions
Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama +3
In this paper, we propose a fast method for exactly enumerating a very large number of all lower cost solutions for various combinatorial problems. Our method is based on backtrack…
Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem
Yuya Masumura, Taihei Oki, Yutaro Yamaguchi
We study the generalized minimum Manhattan network (GMMN) problem: given a set of pairs of two points in the Euclidean plane , we are required to find a minimum-l…
Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice --- Continuous Greedy Algorithm on Median Complex ---
Takanori Maehara, So Nakashima, Yutaro Yamaguchi
We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Since a distributive lattice i…
Stochastic Monotone Submodular Maximization with Queries
Takanori Maehara, Yutaro Yamaguchi
We study a stochastic variant of monotone submodular maximization problem as follows. We are given a monotone submodular function as an objective function and a feasible domain def…
Finding a Shortest Non-zero Path in Group-Labeled Graphs
Yoichi Iwata, Yutaro Yamaguchi
We study a constrained shortest path problem in group-labeled graphs with nonnegative edge length, called the shortest non-zero path problem. Depending on the group in question, th…
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…
Stochastic Packing Integer Programs with Few Queries
Takanori Maehara, Yutaro Yamaguchi
We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entr…
0/1/all CSPs, Half-Integral -path Packing, and Linear-Time FPT Algorithms
Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida
A recent trend in the design of FPT algorithms is exploiting the half-integrality of LP relaxations. In other words, starting with a half-integral optimal solution to an LP relaxat…