research
∙
08/24/2023
Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions
We consider the Shortest Odd Path problem, where given an undirected gra...
share
research
∙
09/29/2022
Matroid Intersection under Restricted Oracles
Matroid intersection is one of the most powerful frameworks of matroid t...
research
∙
08/24/2022
Maintaining Optimality in Assignment Problem against Weight Updates around Vertices
We consider a dynamic situation in the weighted bipartite matching probl...
research
∙
02/09/2022
Hypergraph characterization of split matroids
We provide a combinatorial study of split matroids, a class that was mot...
research
∙
01/20/2022
Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions
In this paper, we propose a fast method for exactly enumerating a very l...
research
∙
07/21/2021
Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems
We study how good a lexicographically maximal solution is in the weighte...
research
∙
04/23/2020
Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem
We study the generalized minimum Manhattan network (GMMN) problem: given...
research
∙
11/24/2019
List colouring of two matroids through reduction to partition matroids
In the list colouring problem for two matroids, we are given matroids M_...
research
∙
07/09/2019
Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice --- Continuous Greedy Algorithm on Median Complex ---
We consider a problem of maximizing a monotone DR-submodular function un...
research
∙
07/09/2019
Stochastic Monotone Submodular Maximization with Queries
We study a stochastic variant of monotone submodular maximization proble...
research
∙
06/10/2019
A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs
Finding a shortest path or cycle in graphs is a fundamental problem. In ...
research
∙
06/10/2019
A Dijkstra-Based Efficient Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs
The parity constrained shortest path problem is a well-known variant tha...
research
∙
11/22/2018
Tight Approximation for Unconstrained XOS Maximization
A set function is called XOS if it can be represented by the maximum of ...
research
∙
06/30/2018
Finding a Path in Group-Labeled Graphs with Two Labels Forbidden
The parity of the length of paths and cycles is a classical and well-stu...
research
∙
04/27/2018
Subgame Perfect Equilibria of Sequential Matching Games
We study a decentralized matching market in which firms sequentially mak...
research
∙
04/27/2018