Kazuhisa Makino

From MaRDI portal
(Redirected from Person:171929)



List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

PublicationDate of PublicationType
Arborescences, colorful forests, and popularity2024-11-28Paper
Generating minimal redundant and maximal irredundant subhypergraphs
Discrete Applied Mathematics
2024-09-26Paper
A polynomial time algorithm for finding a minimum 4-partition of a submodular function
Mathematical Programming. Series A. Series B
2024-09-19Paper
Recognizing distributed approval voting forms and correspondences
Annals of Operations Research
2024-07-16Paper
Envy-free relaxations for goods, chores, and mixed items
Theoretical Computer Science
2024-06-03Paper
A polynomial time algorithm for finding a minimum 4-partition of a submodular function2024-05-14Paper
Hypergraph Horn functions
SIAM Journal on Discrete Mathematics
2024-05-08Paper
A fair and truthful mechanism with limited subsidy
Games and Economic Behavior
2024-04-30Paper
Maximally satisfying lower quotas in the hospitals/residents problem with ties2024-04-23Paper
Online scheduling on identical machines with a metric state space2024-04-23Paper
Matroid Horn functions
Journal of Combinatorial Theory. Series A
2024-01-15Paper
Computing Remoteness Functions of Moore, Wythoff, and Euclid's games2023-11-05Paper
Reallocation problems with minimum completion time
Lecture Notes in Computer Science
2023-08-10Paper
A 3/4 differential approximation algorithm for traveling salesman problem
Lecture Notes in Computer Science
2023-08-04Paper
Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas
Algorithmic Game Theory
2023-07-28Paper
Fair ride allocation on a line
Algorithmic Game Theory
2023-07-28Paper
A fast and simple algorithm for identifying 2-monotonic positive Boolean functions2023-03-21Paper
scientific article; zbMATH DE number 7650261 (Why is no real title available?)
(available as arXiv preprint)
2023-02-03Paper
Trade-offs among degree, diameter, and number of paths
Discrete Applied Mathematics
2023-01-11Paper
Boolean analysis of incomplete examples
Algorithm Theory — SWAT'96
2022-12-09Paper
The Steiner Problem for Count Matroids
Lecture Notes in Computer Science
2022-10-13Paper
Minimizing submodular functions on diamonds via generalized fractional matroid matchings
Journal of Combinatorial Theory. Series B
2022-09-23Paper
Unique key Horn functions
Theoretical Computer Science
2022-06-13Paper
Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs2022-05-11Paper
Finding Sparse Solutions for Packing and Covering Semidefinite Programs
SIAM Journal on Optimization
2022-04-20Paper
Posimodular function optimization
Algorithmica
2022-03-22Paper
Approximating minimum representations of key Horn functions
SIAM Journal on Computing
2022-03-11Paper
On the Sprague-Grundy function of extensions of proper \textsc{nim}
International Journal of Game Theory
2021-09-24Paper
Optimal matroid partitioning problems
Algorithmica
2021-06-11Paper
Generating clause sequences of a CNF formula
Theoretical Computer Science
2021-01-19Paper
Optimal matroid partitioning problems
(available as arXiv preprint)
2020-11-25Paper
Recognizing distributed approval voting forms and correspondences2020-10-29Paper
Enumerating vertices of \(0/1\)-polyhedra associated with \(0/1\)-totally unimodular matrices
(available as arXiv preprint)
2020-08-25Paper
Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
SIAM Journal on Discrete Mathematics
2020-03-26Paper
Surrogate optimization for \(p\)-norms
Discrete Optimization
2019-11-28Paper
Sprague-Grundy function of matroids and related hypergraphs
Theoretical Computer Science
2019-11-13Paper
Deterministic random walks on finite graphs
2012 Proceedings of the Ninth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)
2019-09-17Paper
Unit cost buyback problem
Theory of Computing Systems
2019-09-05Paper
Online knapsack problem under concave functions
Theoretical Computer Science
2019-08-20Paper
Sprague-Grundy function of symmetric hypergraphs
Journal of Combinatorial Theory. Series A
2019-06-25Paper
Proportional cost buyback problem with weight bounds
Theoretical Computer Science
2019-06-25Paper
A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
Information and Computation
2019-05-29Paper
A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
Algorithmica
2019-05-17Paper
Ranking top-k trees in tree-based phylogenetic networks2019-04-28Paper
Online Knapsack Problem Under Concave Functions
Frontiers in Algorithmics
2019-04-26Paper
On the Sprague-Grundy function of compound games2019-03-19Paper
Total dual integrality of the linear complementarity problem
Annals of Operations Research
2019-03-06Paper
Approximation schemes for stochastic mean payoff games with perfect information and few random positions
Algorithmica
2019-01-11Paper
Parameterized edge Hamiltonicity
Discrete Applied Mathematics
2018-09-17Paper
Optimal composition ordering problems for piecewise linear functions
Algorithmica
2018-07-25Paper
A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
Dynamic Games and Applications
2018-06-05Paper
Surrogate optimization for \(p\)-norms2018-04-19Paper
scientific article; zbMATH DE number 6861975 (Why is no real title available?)
(available as arXiv preprint)
2018-04-19Paper
Autark assignments of Horn CNFs
Japan Journal of Industrial and Applied Mathematics
2018-04-12Paper
On the Sprague-Grundy function of \textsc{Exact} \(k\)-\textsc{Nim}
Discrete Applied Mathematics
2018-03-21Paper
Linear satisfiability preserving assignments
Journal of Artificial Intelligence Research
2018-03-07Paper
A convex programming-based algorithm for mean payoff stochastic games with perfect information
Optimization Letters
2017-12-15Paper
Strong duality in Horn minimization2017-11-22Paper
Parameterized complexity of sparse linear complementarity problems
Algorithmica
2017-10-10Paper
Parameterized complexity of sparse linear complementarity problems2017-09-29Paper
Posimodular function optimization
Lecture Notes in Computer Science
2017-09-22Paper
A representation of antimatroids by Horn rules and its application to educational systems
Journal of Mathematical Psychology
2017-09-15Paper
Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden \(2 \times 2\) subgames
International Journal of Game Theory
2017-04-27Paper
A nested family of \(k\)-total effective rewards for positional games
International Journal of Game Theory
2017-04-12Paper
A multiplicative weights update algorithm for packing and covering semi-infinite linear programs
Approximation and Online Algorithms
2017-04-04Paper
Markov decision processes and stochastic games with total effective payoff2017-01-24Paper
Tetris Hypergraphs and Combinations of Impartial Games2017-01-10Paper
Proportional Cost Buyback Problem with Weight Bounds
Combinatorial Optimization and Applications
2016-02-05Paper
The Linear Complementarity Problems with a Few Variables per Constraint
Mathematics of Operations Research
2016-01-29Paper
Trichotomy for integer linear systems based on their sign patterns
Discrete Applied Mathematics
2016-01-21Paper
Online minimization knapsack problem
Theoretical Computer Science
2015-12-08Paper
On randomized fictitious play for approximating saddle points over convex sets
Algorithmica
2015-10-19Paper
Deductive inference for the interiors and exteriors of Horn theories
ACM Transactions on Computational Logic
2015-09-17Paper
Parameterized Algorithms for Parity Games
Mathematical Foundations of Computer Science 2015
2015-09-16Paper
A potential reduction algorithm for ergodic two-person zero-sum limiting average payoff stochastic games
Combinatorial Optimization and Applications
2015-09-11Paper
Parameterized edge Hamiltonicity
Lecture Notes in Computer Science
2015-09-09Paper
Deterministic random walks on finite graphs
Random Structures & Algorithms
2015-07-23Paper
On the Sprague-Grundy Function of Tetris Extensions of Proper {\sc Nim}2015-04-27Paper
Efficient generation of all regular non-dominated coteries
Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing
2015-03-03Paper
Online unweighted knapsack problem with removal cost
Algorithmica
2015-01-19Paper
Randomized algorithms for online knapsack problems
Theoretical Computer Science
2014-12-02Paper
Augmenting edge-connectivity between vertex subsets
Algorithmica
2014-11-19Paper
Online removable knapsack problem under convex function
Theoretical Computer Science
2014-06-06Paper
On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
Operations Research Letters
2014-05-14Paper
Randomized algorithms for removable online knapsack problems
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
2014-04-03Paper
Robust matchings and matroid intersections
SIAM Journal on Discrete Mathematics
2014-01-21Paper
Robust independence systems
SIAM Journal on Discrete Mathematics
2014-01-21Paper
Unit cost buyback problem
Algorithms and Computation
2014-01-14Paper
Nash equilibria with minimum potential in undirected broadcast games
Theoretical Computer Science
2014-01-09Paper
Derandomizing the HSSW algorithm for 3-SAT
Algorithmica
2013-11-11Paper
On canonical forms for zero-sum stochastic mean payoff games
Dynamic Games and Applications
2013-09-16Paper
How to collect balls moving in the Euclidean plane2013-08-30Paper
A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and a few random positions
Lecture Notes in Computer Science
2013-08-06Paper
On randomized fictitious play for approximating saddle points over convex sets
Lecture Notes in Computer Science
2013-06-11Paper
Sparse Linear Complementarity Problems
Lecture Notes in Computer Science
2013-06-07Paper
Computing knapsack solutions with cardinality robustness
Japan Journal of Industrial and Applied Mathematics
2012-12-28Paper
Caching is hard -- even in the fault model
Algorithmica
2012-12-06Paper
Online knapsack problem with removal cost
Lecture Notes in Computer Science
2012-09-25Paper
Trichotomy for integer linear systems based on their sign patterns2012-08-23Paper
Nash equilibria with minimum potential in undirected broadcast games
WALCOM: Algorithms and Computation
2012-06-08Paper
Finding simplices containing the origin in two and three dimensions
International Journal of Computational Geometry & Applications
2012-04-19Paper
On Nash equilibria and improvement cycles in pure positional strategies for chess-like and backgammon-like \(n\)-person games
Discrete Mathematics
2012-04-13Paper
Online removable knapsack with limited cuts
Theoretical Computer Science
2012-04-03Paper
Computing knapsack solutions with cardinality robustness
Algorithms and Computation
2011-12-16Paper
On the readability of monotone Boolean formulae
Journal of Combinatorial Optimization
2011-12-15Paper
Logical analysis of data: classification with justification
Annals of Operations Research
2011-11-17Paper
Nash-solvable two-person symmetric cycle game forms
Discrete Applied Mathematics
2011-10-27Paper
An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
Theoretical Computer Science
2011-09-12Paper
Derandomizing HSSW algorithm for 3-SAT
Lecture Notes in Computer Science
2011-08-17Paper
Robust independence systems
Automata, Languages and Programming
2011-07-06Paper
Stochastic mean payoff games: smoothed analysis and approximation schemes
Automata, Languages and Programming
2011-07-06Paper
Left-to-right multiplication for monotone Boolean dualization
SIAM Journal on Computing
2011-04-04Paper
Nonadaptive broadcasting in trees
Networks
2011-03-16Paper
On the Boolean connectivity problem for Horn relations
Discrete Applied Mathematics
2010-11-25Paper
An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
Theory and Applications of Satisfiability Testing – SAT 2010
2010-09-29Paper
Robust matchings and matroid intersections
Algorithms – ESA 2010
2010-09-06Paper
Caching is hard -- even in the fault model
Algorithms – ESA 2010
2010-09-06Paper
New results on monotone dualization and generating hypergraph transversals
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
2010-08-05Paper
A pumping algorithm for ergodic stochastic mean payoff games with perfect information
Integer Programming and Combinatorial Optimization
2010-06-22Paper
Minimum transversals in posimodular systems
SIAM Journal on Discrete Mathematics
2010-06-01Paper
Posi-modular systems with modulotone requirements under permutation constraints
Discrete Mathematics, Algorithms and Applications
2010-05-19Paper
Online minimization knapsack problem
Approximation and Online Algorithms
2010-05-11Paper
Acyclic, or totally tight, two-person game forms: characterization and main properties
Discrete Mathematics
2010-04-27Paper
On effectivity functions of game forms
Games and Economic Behavior
2010-03-10Paper
Online Knapsack Problems with Limited Cuts
Algorithms and Computation
2009-12-17Paper
Posi-modular systems with modulotone requirements under permutation constraints
Algorithms and Computation
2009-12-17Paper
Minimal and locally minimal games and game forms
Discrete Mathematics
2009-12-10Paper
Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
Lecture Notes in Computer Science
2009-10-29Paper
On the Readability of Monotone Boolean Formulae
Lecture Notes in Computer Science
2009-07-23Paper
A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
Automata, Languages and Programming
2009-07-14Paper
scientific article; zbMATH DE number 5548206 (Why is no real title available?)2009-04-28Paper
On the fractional chromatic number of monotone self-dual Boolean functions
Discrete Mathematics
2009-04-09Paper
On the Fractional Chromatic Number of Monotone Self-dual Boolean Functions
Frontiers in Algorithmics
2009-03-10Paper
On the Boolean Connectivity Problem for Horn Relations
Theory and Applications of Satisfiability Testing – SAT 2007
2009-03-10Paper
Generating Minimal k-Vertex Connected Spanning Subgraphs
Lecture Notes in Computer Science
2009-03-06Paper
Deductive Inference for the Interiors and Exteriors of Horn Theories
Algorithms and Computation
2009-01-29Paper
On computing all abductive explanations from a propositional Horn theory
Journal of the ACM
2008-12-21Paper
Minimum Cost Source Location Problems with Flow Requirements
LATIN 2006: Theoretical Informatics
2008-09-18Paper
Minimizing a monotone concave function with laminar covering constraints
Discrete Applied Mathematics
2008-09-10Paper
Computational aspects of monotone dualization: a brief survey
Discrete Applied Mathematics
2008-09-10Paper
On Berge Multiplication for Monotone Boolean Dualization
Automata, Languages and Programming
2008-08-28Paper
Generating cut conjunctions in graphs and related problems
Algorithmica
2008-07-01Paper
A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames
Computer Science – Theory and Applications
2008-06-05Paper
ENUMERATING SPANNING AND CONNECTED SUBSETS IN GRAPHS AND MATROIDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
Journal of the Operations Research Society of Japan
2008-04-29Paper
Minimum cost source location problems with flow requirements
Algorithmica
2008-04-23Paper
Enumerating Spanning and Connected Subsets in Graphs and Matroids
Lecture Notes in Computer Science
2008-03-11Paper
Minimum Transversals in Posi-modular Systems
Lecture Notes in Computer Science
2008-03-11Paper
Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
Theoretical Computer Science
2007-07-16Paper
Computer Science Logic
Lecture Notes in Computer Science
2007-06-21Paper
Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
Discrete Applied Mathematics
2007-02-19Paper
An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
Discrete Applied Mathematics
2007-01-09Paper
How to collect balls moving in the Euclidean plane
Discrete Applied Mathematics
2007-01-09Paper
Minimum edge ranking spanning trees of split graphs
Discrete Applied Mathematics
2007-01-09Paper
Algorithms and Computation
Lecture Notes in Computer Science
2006-11-14Paper
Algorithms and Computation
Lecture Notes in Computer Science
2006-11-14Paper
A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
Journal of the Operations Research Society of Japan
2006-06-14Paper
On the Complexity of Some Enumeration Problems for Matroids
SIAM Journal on Discrete Mathematics
2006-06-01Paper
Algorithm Theory - SWAT 2004
Lecture Notes in Computer Science
2005-09-07Paper
Mathematical Foundations of Computer Science 2004
Lecture Notes in Computer Science
2005-08-22Paper
scientific article; zbMATH DE number 2163024 (Why is no real title available?)2005-04-29Paper
scientific article; zbMATH DE number 2152473 (Why is no real title available?)2005-04-05Paper
Dual-bounded generating problems: Weighted transversals of a hypergraph
Discrete Applied Mathematics
2004-08-19Paper
scientific article; zbMATH DE number 2086380 (Why is no real title available?)2004-08-11Paper
Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2
Discrete Mathematics
2004-08-06Paper
scientific article; zbMATH DE number 2038737 (Why is no real title available?)2004-02-08Paper
Interior and exterior functions of positive Boolean functions.
Discrete Applied Mathematics
2003-09-22Paper
scientific article; zbMATH DE number 1979519 (Why is no real title available?)2003-09-14Paper
Finding essential attributes from binary data
Annals of Mathematics and Artificial Intelligence
2003-08-21Paper
On maximal frequent and minimal infrequent sets in binary matrices
Annals of Mathematics and Artificial Intelligence
2003-08-21Paper
Variations on extending partially defined Boolean functions with missing bits.
Information and Computation
2003-08-13Paper
New Results on Monotone Dualization and Generating Hypergraph Transversals
SIAM Journal on Computing
2003-06-19Paper
Inferring minimal functional dependencies in Horn and q-Horn theories
Annals of Mathematics and Artificial Intelligence
2003-06-09Paper
Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
Discrete Applied Mathematics
2003-03-09Paper
A simple matching algorithm for regular bipartite graphs.
Information Processing Letters
2003-01-21Paper
Logical analysis of data with decomposable structures.
Theoretical Computer Science
2003-01-21Paper
Recognition and dualization of disguised bidual Horn functions.
Information Processing Letters
2003-01-21Paper
Max- and Min-neighborhood monopolies
Algorithmica
2002-12-01Paper
scientific article; zbMATH DE number 1759476 (Why is no real title available?)2002-11-25Paper
A linear time algorithm for recognizing regular Boolean functions
Journal of Algorithms
2002-09-30Paper
Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
SIAM Journal on Computing
2002-09-29Paper
Locating sources to meet flow demands in undirected networks
Journal of Algorithms
2002-09-11Paper
Logical analysis of binary data with missing bits
Artificial Intelligence
2002-07-24Paper
Computing intersections of Horn theories for reasoning with models
Artificial Intelligence
2002-07-24Paper
On functional dependencies in \(q\)-Horn theories
Artificial Intelligence
2002-07-24Paper
scientific article; zbMATH DE number 1696655 (Why is no real title available?)2002-07-22Paper
scientific article; zbMATH DE number 1754587 (Why is no real title available?)2002-06-12Paper
scientific article; zbMATH DE number 1741097 (Why is no real title available?)2002-05-15Paper
Disjunctions of Horn theories and their cores
SIAM Journal on Computing
2002-04-23Paper
Decision lists and related Boolean functions
Theoretical Computer Science
2002-03-03Paper
Transformations on regular nondominated coteries and their applications
SIAM Journal on Discrete Mathematics
2001-11-11Paper
scientific article; zbMATH DE number 1670855 (Why is no real title available?)2001-11-11Paper
On the difference of Horn theories
Journal of Computer and System Sciences
2001-10-30Paper
A satisfiability formulation of problems on level graphs2001-09-24Paper
On minimum edge ranking spanning trees
Journal of Algorithms
2001-07-23Paper
scientific article; zbMATH DE number 1617284 (Why is no real title available?)2001-07-11Paper
scientific article; zbMATH DE number 1617268 (Why is no real title available?)2001-07-11Paper
Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
SIAM Journal on Computing
2001-06-21Paper
scientific article; zbMATH DE number 1522935 (Why is no real title available?)2001-03-05Paper
scientific article; zbMATH DE number 1555949 (Why is no real title available?)2001-01-24Paper
Minimum self-dual decompositions of positive dual-minor Boolean functions
Discrete Applied Mathematics
2000-03-02Paper
scientific article; zbMATH DE number 1398053 (Why is no real title available?)2000-02-03Paper
scientific article; zbMATH DE number 1398086 (Why is no real title available?)2000-02-03Paper
Inner-core and outer-core functions of partially defined Boolean functions
Discrete Applied Mathematics
2000-01-17Paper
Bidual Horn functions and extensions
Discrete Applied Mathematics
2000-01-17Paper
scientific article; zbMATH DE number 1372651 (Why is no real title available?)1999-12-01Paper
scientific article; zbMATH DE number 1304333 (Why is no real title available?)1999-11-07Paper
Horn Extensions of a Partially Defined Boolean Function
SIAM Journal on Computing
1999-10-28Paper
scientific article; zbMATH DE number 1303023 (Why is no real title available?)1999-06-17Paper
Double Horn functions
Information and Computation
1999-05-16Paper
Functional dependencies in Horn theories
Artificial Intelligence
1999-04-28Paper
Error-free and best-fit extensions of partially defined Boolean functions
Information and Computation
1998-07-27Paper
A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
Journal of Algorithms
1998-06-23Paper
scientific article; zbMATH DE number 1104349 (Why is no real title available?)1998-05-25Paper
scientific article; zbMATH DE number 1104330 (Why is no real title available?)1998-04-01Paper
scientific article; zbMATH DE number 1136094 (Why is no real title available?)1998-04-01Paper
The Maximum Latency and Identification of Positive Boolean Functions
SIAM Journal on Computing
1998-02-10Paper
Positive and Horn decomposability of partially defined Boolean functions
Discrete Applied Mathematics
1997-10-29Paper
Interior and exterior functions of Boolean functions
Discrete Applied Mathematics
1997-01-27Paper


Research outcomes over time


This page was built for person: Kazuhisa Makino