Naonori Kakimura

Orcid: 0000-0002-3918-3479

According to our database1, Naonori Kakimura authored at least 73 papers between 2007 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Randomized counter-based algorithms for frequency estimation over data streams in O(log⁡log⁡N) space.
Theor. Comput. Sci., February, 2024

Reconfiguration of labeled matchings in triangular grid graphs.
CoRR, 2024

On Approximating the Weighted Region Problem in Square Tessellations.
CoRR, 2024

Parameterized Complexity of Submodular Minimization Under Uncertainty.
Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem.
Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023
On reachable assignments under dichotomous preferences.
Theor. Comput. Sci., November, 2023

Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams.
ACM Trans. Algorithms, January, 2023

Algorithmic Theory of Qubit Routing.
Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Bandit Task Assignment with Unknown Processing Time.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Rerouting Planar Curves and Disjoint Paths.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Deterministic Primal-Dual Algorithms for Online k-Way Matching with Delays.
Proceedings of the Computing and Combinatorics - 29th International Conference, 2023

2022
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.
SIAM J. Discret. Math., 2022

Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model.
SIAM J. Discret. Math., 2022

A parameterized view to the robust recoverable base problem of matroids under structural uncertainty.
Oper. Res. Lett., 2022

Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization.
Theory Comput. Syst., 2022

Submodular reassignment problem for reallocating agents to tasks with synergy effects.
Discret. Optim., 2022

Online Task Assignment Problems with Reusable Resources.
Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

Reforming an Envy-Free Matching.
Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021
Market Pricing for Matroid Rank Valuations.
SIAM J. Discret. Math., 2021

Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint.
Algorithmica, 2021

Dynamic Bipartite Matching Market with Arrivals and Departures.
Proceedings of the Web and Internet Economics - 17th International Conference, 2021

A Parameter-Free Algorithm for Misspecified Linear Contextual Bandits.
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020
Complexity of the multi-service center problem.
Theor. Comput. Sci., 2020

Spectral aspects of symmetric matrix signings.
Discret. Optim., 2020

The b-branching problem in digraphs.
Discret. Appl. Math., 2020

Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint.
Algorithmica, 2020

Delay and Cooperation in Nonstochastic Linear Bandits.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019
Exact and approximation algorithms for weighted matroid intersection.
Math. Program., 2019

Reconfiguration of maximum-weight b-matchings in a graph.
J. Comb. Optim., 2019

Online Spectral Approximation in Random Order Streams.
CoRR, 2019

Total dual integrality of the linear complementarity problem.
Ann. Oper. Res., 2019

Minimum-Cost b-Edge Dominating Sets on Trees.
Algorithmica, 2019

Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising.
Proceedings of the PRICAI 2019: Trends in Artificial Intelligence, 2019

Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries.
Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2019

Improved Regret Bounds for Bandit Combinatorial Optimization.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018
Maximum lifetime coverage problem with battery recovery effect.
Sustain. Comput. Informatics Syst., 2018

The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs.
J. Comb. Theory B, 2018

Regret Bounds for Online Portfolio Selection with a Cardinality Constraint.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Causal Bandits with Propagating Inference.
Proceedings of the 35th International Conference on Machine Learning, 2018

Boosting PageRank Scores by Optimizing Internal Link Structure.
Proceedings of the Database and Expert Systems Applications, 2018

Finding a Dense Subgraph with Sparse Cut.
Proceedings of the 27th ACM International Conference on Information and Knowledge Management, 2018

Online Regression with Partial Information: Generalization and Linear Projection.
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017
Efficient stabilization of cooperative matching games.
Theor. Comput. Sci., 2017

Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs.
SIAM J. Discret. Math., 2017

Parameterized Complexity of Sparse Linear Complementarity Problems.
Algorithmica, 2017

Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization.
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017

Reducing Recovery Error in Compressive Sensing with Limited Number of Base Stations.
Proceedings of the 2017 IEEE Global Communications Conference, 2017

Tight Approximability of the Server Allocation Problem for Real-Time Applications.
Proceedings of the Algorithmic Aspects of Cloud Computing - Third International Workshop, 2017

2016
Coloring immersion-free graphs.
J. Comb. Theory B, 2016

Maximizing Time-Decaying Influence in Social Networks.
Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2016

2015
Fixed-parameter tractability for subset feedback set problems with parity constraints.
Theor. Comput. Sci., 2015

The Linear Complementarity Problems with a Few Variables per Constraint.
Math. Oper. Res., 2015

Threshold Influence Model for Allocating Advertising Budgets.
Proceedings of the 32nd International Conference on Machine Learning, 2015

2014
Matching Problems with Delta-Matroid Constraints.
SIAM J. Discret. Math., 2014

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm.
Proceedings of the 31th International Conference on Machine Learning, 2014

Maximum lifetime coverage problems with battery recovery effects.
Proceedings of the IEEE Global Communications Conference, 2014

2013
Robust Independence Systems.
SIAM J. Discret. Math., 2013

Half-integral packing of odd cycles through prescribed vertices.
Comb., 2013

Sparse Linear Complementarity Problems.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2012
Packing Directed Circuits through Prescribed Vertices Bounded Fractionally.
SIAM J. Discret. Math., 2012

Packing cycles through prescribed vertices under modularity constraints.
Adv. Appl. Math., 2012

Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011
Packing cycles through prescribed vertices.
J. Comb. Theory B, 2011

Computing Knapsack Solutions with Cardinality Robustness.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Set Covering with Ordered Replacement: Additive and Multiplicative Gaps.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

2010
Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem.
J. Comb. Theory B, 2010

2008
Solving linear programs from sign patterns.
Math. Program., 2008

2007
Computing the inertia from sign patterns.
Math. Program., 2007

Sign-Solvable Linear Complementarity Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2007


  Loading...