4 citations · 12 across the 21 of their papers we have counts for
22 papers
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…
Hypergraph characterization of split matroids
Kristóf Bérczi, Tamás Király, Tamás Schwarcz +2
We provide a combinatorial study of split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. A nice feature of split mat…
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…
Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
We study how good a lexicographically maximal solution is in the weighted matching and matroid intersection problems. A solution is lexicographically maximal if it takes as many he…
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…
List colouring of two matroids through reduction to partition matroids
Kristóf Bérczi, Tamás Schwarcz, Yutaro Yamaguchi
In the list coloring problem for two matroids, we are given matroids and on the same ground set , and the goal is to determine the smal…
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…
Finding a Path with Two Labels Forbidden in Group-Labeled Graphs
Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi
The parity of the length of paths and cycles is a classical and well-studied topic in graph theory and theoretical computer science. The parity constraints can be extended to label…
Subgame Perfect Equilibria of Sequential Matching Games
Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi
We study a decentralized matching market in which firms sequentially make offers to potential workers. For each offer, the worker can choose "accept" or "reject," but the decision…
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…
Antimatroids Induced by Matchings
Yasushi Kawase, Yutaro Yamaguchi
We explore novel connections between antimatroids and matchings in bipartite graphs. In particular, we prove that a combinatorial structure induced by stable matchings or maximum-w…
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…
Making Bipartite Graphs DM-irreducible
Kristóf Bérczi, Satoru Iwata, Jun Kato +1
The Dulmage--Mendelsohn decomposition (or the DM-decomposition) gives a unique partition of the vertex set of a bipartite graph reflecting the structure of all the maximum matching…
Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions
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 co…