19 Search Results for "Kawase, Yasushi"

Document
DOI: 10.4230/LIPIcs.STACS.2026.43
Stealing from the Dragon’s Hoard: Online Unbounded Knapsack With Removal

Authors: Matthias Gehnen and Moritz Stocker

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We introduce the Online Unbounded Knapsack Problem with Removal, a variation of the well-known Online Knapsack Problem. Items, each with a weight and value, arrive online and an algorithm must decide on whether or not to pack them into a knapsack with a fixed weight limit. An item may be packed an arbitrary number of times and items may be removed from the knapsack at any time without cost. The goal is to maximize the total value of items packed, while respecting a weight limit. We show that this is one of the very few natural online knapsack variants that allow for competitive deterministic algorithms in the general setting, by providing an algorithm with competitivity 1.6911. We complement this with a lower bound of 1.5877. We also analyze the proportional setting, where the weight and value of any single item agree, and show that deterministic algorithms can be exactly 3/2-competitive. Lastly, we give lower and upper bounds of 6/5 and 4/3 on the competitivity of randomized algorithms in this setting.
Cite as

Matthias Gehnen and Moritz Stocker. Stealing from the Dragon’s Hoard: Online Unbounded Knapsack With Removal. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gehnen_et_al:LIPIcs.STACS.2026.43,
  author =	{Gehnen, Matthias and Stocker, Moritz},
  title =	{{Stealing from the Dragon’s Hoard: Online Unbounded Knapsack With Removal}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.43},
  URN =		{urn:nbn:de:0030-drops-255327},
  doi =		{10.4230/LIPIcs.STACS.2026.43},
  annote =	{Keywords: online problems, online knapsack, unbounded knapsack, removal}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.38
Fairness and Efficiency in Two-Sided Matching Markets

Authors: Pallavi Jain, Palash Jha, and Shubham Solanki

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We propose a new fairness notion, motivated by the practical challenge of allocating teaching assistants (TAs) to courses in a department. Each course requires a certain number of TAs and each TA has preferences over the courses they want to assist. Similarly, each course instructor has preferences over the TAs who applied for their course. We demand fairness and efficiency for both sides separately, giving rise to the following criteria: (i) every course gets the required number of TAs and the average utility of the assigned TAs meets a threshold; (ii) the allocation of courses to TAs is envy-free, where a TA envies another TA if the former prefers the latter’s course and has a higher or equal grade in that course. Note that the definition of envy-freeness here differs from the one in the literature, and we call it merit-based envy-freeness. We show that the problem of finding a merit-based envy-free and efficient matching is NP-hard even for very restricted settings, such as two courses and uniform valuations; constant degree, constant capacity of TAs for every course, valuations in the range {0,1,2,3}, identical valuations from TAs, and even more. To find tractable results, we consider some restricted instances, such as, strict valuation of TAs for courses, the difference between the number of positively valued TAs for a course and the capacity, the number of positively valued TAs/courses, types of valuation functions, and obtained some polynomial-time solvable cases, showing the contrast with intractable results. We further studied the problem in the paradigm of parameterized algorithms and designed some exact and approximation algorithms.
Cite as

Pallavi Jain, Palash Jha, and Shubham Solanki. Fairness and Efficiency in Two-Sided Matching Markets. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.FSTTCS.2025.38,
  author =	{Jain, Pallavi and Jha, Palash and Solanki, Shubham},
  title =	{{Fairness and Efficiency in Two-Sided Matching Markets}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.38},
  URN =		{urn:nbn:de:0030-drops-251186},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.38},
  annote =	{Keywords: Fair Matching, Envy-Freeness, Efficiency}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.41
Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

Authors: Yasushi Kawase, Bodhayan Roy, and Mohammad Azharuddin Sanpui

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
This paper explores the fair allocation of indivisible items in a multidimensional setting, motivated by the need to address fairness in complex environments where agents assess bundles according to multiple criteria. Such multidimensional settings are not merely of theoretical interest but are central to many real-world applications. For example, cloud computing resources are evaluated based on multiple criteria such as CPU cores, memory, and network bandwidth. In such cases, traditional one-dimensional fairness notions fail to capture fairness across multiple attributes. To address these challenges, we study two relaxed variants of envy-freeness: weak simultaneously envy-free up to c goods (weak sEFc) and strong simultaneously envy-free up to c goods (strong sEFc), which accommodate the multidimensionality of agents’ preferences. Under the weak notion, for every pair of agents and for each dimension, any perceived envy can be eliminated by removing, if necessary, a different set of goods from the envied agent’s allocation. In contrast, the strong version requires selecting a single set of goods whose removal from the envied bundle simultaneously eliminates envy in every dimension. We provide upper and lower bounds on the relaxation parameter c that guarantee the existence of weak or strong sEFc allocations, where these bounds are independent of the total number of items. In addition, we present algorithms for checking whether a weak or strong sEFc allocation exists. Moreover, we establish NP-hardness results for checking the existence of weak sEF1 and strong sEF1 allocations.
Cite as

Yasushi Kawase, Bodhayan Roy, and Mohammad Azharuddin Sanpui. Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.FSTTCS.2025.41,
  author =	{Kawase, Yasushi and Roy, Bodhayan and Sanpui, Mohammad Azharuddin},
  title =	{{Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{41:1--41:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.41},
  URN =		{urn:nbn:de:0030-drops-251210},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.41},
  annote =	{Keywords: Fair allocation, Envy-free up to one good, Multi-dimensional criteria, Linear programming, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.92
Incremental Maximization for a Broad Class of Objectives

Authors: Yann Disser and David Weckbecker

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider incremental maximization problems, where the solution has to be built up gradually by adding elements one after the other. In every step, the incremental solution must be competitive, compared against the optimum solution of the current cardinality. We prove that a competitive solution always exists when the objective function is monotone and β-accountable, by providing a scaling algorithm that guarantees a constant competitive ratio. This generalizes known results and, importantly, yields the first competitive algorithm for the natural class of monotone and subadditive objective functions.
Cite as

Yann Disser and David Weckbecker. Incremental Maximization for a Broad Class of Objectives. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 92:1-92:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ESA.2025.92,
  author =	{Disser, Yann and Weckbecker, David},
  title =	{{Incremental Maximization for a Broad Class of Objectives}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{92:1--92:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.92},
  URN =		{urn:nbn:de:0030-drops-245613},
  doi =		{10.4230/LIPIcs.ESA.2025.92},
  annote =	{Keywords: incremental maximization, competitive analysis, subadditive functions}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.41
Scheduling on Identical Machines with Setup Time and Unknown Execution Time

Authors: Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, and Hanna Sumita

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
In this study, we investigate a scheduling problem on identical machines in which jobs require initial setup before execution. We assume that an algorithm can dynamically form a batch (i.e., a collection of jobs to be processed together) from the remaining jobs. The setup time is modeled as a known monotone function of the set of jobs within a batch, while the execution time of each job remains unknown until completion. This uncertainty poses significant challenges for minimizing the makespan. We address these challenges by considering two scenarios: each job batch must be assigned to a single machine, or a batch may be distributed across multiple machines. For both scenarios, we analyze settings with and without preemption. Across these four settings, we design online algorithms that achieve asymptotically optimal competitive ratios with respect to both the number of jobs and the number of machines.
Cite as

Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, and Hanna Sumita. Scheduling on Identical Machines with Setup Time and Unknown Execution Time. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.WADS.2025.41,
  author =	{Kawase, Yasushi and Makino, Kazuhisa and Phan, Vinh Long and Sumita, Hanna},
  title =	{{Scheduling on Identical Machines with Setup Time and Unknown Execution Time}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.41},
  URN =		{urn:nbn:de:0030-drops-242728},
  doi =		{10.4230/LIPIcs.WADS.2025.41},
  annote =	{Keywords: Online scheduling, Competitive analysis, Makespan minimization, Identical machines scheduling}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.12
Online Knapsack Problems with Estimates

Authors: Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to. When you are aware of all possible events and their costs at the beginning of the year, you can select the subset of the possible events that maximizes your happiness and is within your budget. On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future. These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic: Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices. We model this problem within the setting of online knapsack problems with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy δ (i.e., when each actual item size can deviate by ± δ from the announced size) for both the simple knapsack (also known as subset sum problem) and the simple knapsack with removability.
Cite as

Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker. Online Knapsack Problems with Estimates. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.12,
  author =	{Balab\'{a}n, Jakub and Gehnen, Matthias and Lotze, Henri and Seesemann, Finn and Stocker, Moritz},
  title =	{{Online Knapsack Problems with Estimates}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.12},
  URN =		{urn:nbn:de:0030-drops-241190},
  doi =		{10.4230/LIPIcs.MFCS.2025.12},
  annote =	{Keywords: Knapsack, Online Knapsack, Removability, Estimate, Prediction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.85
Towards the Proximity Conjecture on Group-Labeled Matroids

Authors: Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Consider a matroid M whose ground set is equipped with a labeling to an abelian group. A basis of M is called F-avoiding if the sum of the labels of its elements is not in a forbidden label set F. Hörsch, Imolay, Mizutani, Oki, and Schwarcz (2024) conjectured that if an F-avoiding basis exists, then any basis can be transformed into an F-avoiding basis by exchanging at most |F| elements. This proximity conjecture is known to hold for certain specific groups; in the case where |F| ≤ 2; or when the matroid is subsequence-interchangeably base orderable (SIBO), which is a weakening of the so-called strongly base orderable (SBO) property. In this paper, we settle the proximity conjecture for sparse paving matroids or in the case where |F| ≤ 4. Related to the latter result, we present the first known example of a non-SIBO matroid. We further address the setting of multiple group-label constraints, showing proximity results for the cases of two labelings, SIBO matroids, matroids representable over a fixed, finite field, and sparse paving matroids.
Cite as

Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi. Towards the Proximity Conjecture on Group-Labeled Matroids. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garamvolgyi_et_al:LIPIcs.ICALP.2025.85,
  author =	{Garamv\"{o}lgyi, D\'{a}niel and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s and Yamaguchi, Yutaro},
  title =	{{Towards the Proximity Conjecture on Group-Labeled Matroids}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{85:1--85:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.85},
  URN =		{urn:nbn:de:0030-drops-234628},
  doi =		{10.4230/LIPIcs.ICALP.2025.85},
  annote =	{Keywords: sparse paving matroid, subsequence-interchangeable base orderability, congruency constraint, multiple labelings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.59
Online Matching with Delays and Size-Based Costs

Authors: Yasushi Kawase and Tomohiro Nakayoshi

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In this paper, we introduce the problem of Online Matching with Delays and Size-based Costs (OMDSC). The OMDSC problem involves m requests arriving online. At any time, a group can be formed by matching any number of requests that have been received but remain unmatched. The cost associated with each group is determined by the waiting time for each request within the group and size-dependent cost. The size-dependent cost is specified by a penalty function. Our goal is to partition all the incoming requests into multiple groups while minimizing the total associated cost. This problem is an extension of the TCP acknowledgment problem proposed by Dooly et al. (J. ACM, 2001). It generalizes the cost model for sending acknowledgments. This study reveals the competitive ratios for a fundamental case, in which the penalty function takes only values of either 0 or 1. We classify such penalty functions into three distinct cases: (i) a fixed penalty of 1 regardless of the group size, (ii) a penalty of 0 if and only if the group size is a multiple of a specific integer k, and (iii) other situations. The problem in case (i) is equivalent to the TCP acknowledgment problem, for which Dooly et al. proposed a 2-competitive algorithm. For case (ii), we first show that natural algorithms that match all remaining requests are Ω(√k)-competitive. We then propose an O(log k / log log k)-competitive deterministic algorithm by carefully managing the match size and timing, and prove its optimality. For any penalty function in case (iii), we demonstrate the non-existence of a competitive online algorithm. Additionally, we discuss competitive ratios for other typical penalty functions that are not restricted to take values of 0 or 1.
Cite as

Yasushi Kawase and Tomohiro Nakayoshi. Online Matching with Delays and Size-Based Costs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.STACS.2025.59,
  author =	{Kawase, Yasushi and Nakayoshi, Tomohiro},
  title =	{{Online Matching with Delays and Size-Based Costs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.59},
  URN =		{urn:nbn:de:0030-drops-228846},
  doi =		{10.4230/LIPIcs.STACS.2025.59},
  annote =	{Keywords: Online matching, competitive analysis, delayed service}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.44
Composition Orderings for Linear Functions and Matrix Multiplication Orderings

Authors: Susumu Kubo, Kazuhisa Makino, and Souta Sakamoto

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We first consider composition orderings for linear functions of one variable. Given n linear functions f_1,… ,f_n: ℝ → ℝ and a constant c ∈ ℝ, the objective is to find a permutation σ:[n] → [n] that minimizes/maximizes f_σ(n)∘⋯∘f_σ(1)(c), where [n] = {1, … , n}. It was first studied in the area of time-dependent scheduling, and known to be solvable in O(n log n) time if all functions are nondecreasing. In this paper, we present a complete characterization of optimal composition orderings for this case, by regarding linear functions as two-dimensional vectors. We also show the equivalence between local and global optimality in optimal composition orderings. Furthermore, by using the characterization above, we provide a fixed-parameter tractable (FPT) algorithm for the composition ordering problem with general linear functions, with respect to the number of decreasing linear functions. We next deal with matrix multiplication as a generalization of composition of linear functions. Given n matrices M₁,… , M_n ∈ ℝ^{m×m} and two vectors w,y ∈ ℝ^m, where m is a positive integer, the objective is to find a permutation σ:[n] → [n] that minimizes/maximizes w^⊤ M_σ(n) ⋯ M_σ(1) y. The matrix multiplication ordering problem has been studied in the context of max-plus algebra, but despite being a natural problem, it has not been explored in the conventional algebra to date. By extending the results for composition orderings for linear functions, we show that the matrix multiplication ordering problem with 2× 2 matrices is solvable in O(n log n) time if all the matrices are simultaneously triangularizable and have nonnegative determinants, and FPT with respect to the number of matrices with negative determinants, if all the matrices are simultaneously triangularizable. As the negative side, we prove that three possible natural generalizations are NP-hard. In addition, we derive the existing result for the minimum matrix multiplication ordering problem with 2 × 2 upper triangular matrices in max-plus algebra, which is an extension of the well-known Johnson’s rule for the two-machine flow shop scheduling, as a corollary of our result in the conventional algebra.
Cite as

Susumu Kubo, Kazuhisa Makino, and Souta Sakamoto. Composition Orderings for Linear Functions and Matrix Multiplication Orderings. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kubo_et_al:LIPIcs.ISAAC.2024.44,
  author =	{Kubo, Susumu and Makino, Kazuhisa and Sakamoto, Souta},
  title =	{{Composition Orderings for Linear Functions and Matrix Multiplication Orderings}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.44},
  URN =		{urn:nbn:de:0030-drops-221717},
  doi =		{10.4230/LIPIcs.ISAAC.2024.44},
  annote =	{Keywords: function composition, matrix multiplication, ordering problem, scheduling}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.105
The Last Success Problem with Samples

Authors: Toru Yoshinaga and Yasushi Kawase

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
The last success problem is an optimal stopping problem that aims to maximize the probability of stopping on the last success in a sequence of independent n Bernoulli trials. In the classical setting where complete information about the distributions is available, Bruss [Bruss, 2000] provided an optimal stopping policy that ensures a winning probability of 1/e. However, assuming complete knowledge of the distributions is unrealistic in many practical applications. This paper investigates a variant of the last success problem where samples from each distribution are available instead of complete knowledge of them. When a single sample from each distribution is allowed, we provide a deterministic policy that guarantees a winning probability of 1/4. This is best possible by the upper bound provided by Nuti and Vondrák [Nuti and Vondr{á}k, 2023]. Furthermore, for any positive constant ε, we show that a constant number of samples from each distribution is sufficient to guarantee a winning probability of 1/e-ε.
Cite as

Toru Yoshinaga and Yasushi Kawase. The Last Success Problem with Samples. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 105:1-105:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{yoshinaga_et_al:LIPIcs.ESA.2024.105,
  author =	{Yoshinaga, Toru and Kawase, Yasushi},
  title =	{{The Last Success Problem with Samples}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{105:1--105:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.105},
  URN =		{urn:nbn:de:0030-drops-211762},
  doi =		{10.4230/LIPIcs.ESA.2024.105},
  annote =	{Keywords: The Last Success Problem, Secretary Problem, Sample Information Model, Optimal Stopping, Online Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.96
Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets

Authors: Yasushi Kawase, Koichi Nishimura, and Hanna Sumita

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study the problem of minimizing a given symmetric strictly convex function over the Minkowski sum of an integral base-polyhedron and an M-convex set. This problem has a hybrid of continuous and discrete structures. This emerges from the problem of allocating mixed goods, consisting of both divisible and indivisible goods, to agents with binary valuations so that the fairness measure, such as the Nash welfare, is maximized. It is known that both an integral base-polyhedron and an M-convex set have similar and nice properties, and the non-hybrid case can be solved in polynomial time. While the hybrid case lacks some of these properties, we show the structure of an optimal solution. Moreover, we exploit a proximity inherent in the problem. Through our findings, we demonstrate that our problem is NP-hard even in the fair allocation setting where all indivisible goods are identical. Moreover, we provide a polynomial-time algorithm for the fair allocation problem when all divisible goods are identical.
Cite as

Yasushi Kawase, Koichi Nishimura, and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ICALP.2024.96,
  author =	{Kawase, Yasushi and Nishimura, Koichi and Sumita, Hanna},
  title =	{{Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{96:1--96:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.96},
  URN =		{urn:nbn:de:0030-drops-202393},
  doi =		{10.4230/LIPIcs.ICALP.2024.96},
  annote =	{Keywords: Integral base-polyhedron, Fair allocation, Matroid}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.32
Online Scheduling on Identical Machines with a Metric State Space

Authors: Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino, and Hanna Sumita

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
This paper introduces an online scheduling problem on m identical machines with a metric state space, which generalizes the classical online scheduling problem on identical machines, the online traveling salesman problem, and the online dial-a-ride problem. Each job is associated with a source state, a destination state, a processing time, and a release time. Each machine can process a job on and after its release time. Before processing a job, a machine needs to change its state to the source state (in a time corresponding to the distance), and after the process of the job, the machine’s state becomes the destination state. While related research deals with a model in which only release times are unknown to the algorithm, this paper focuses on a general model in which destination states and processing times are also unknown. The main result of this paper is to propose a O(log m/log log m)-competitive online algorithm for the problem, which is best possible. A key approach is to divide the difficulty of the problem. To cope with unknown release times, we provide frameworks to produce a min{2ρ+1/2, ρ+2}-competitive algorithm using a ρ-competitive algorithm for a basic case where all jobs are released at time 0. Then, focusing on unknown destination states and processing times, we construct an O(log m/log log m)-competitive algorithm for the basic case. We also provide improved algorithms for some special cases.
Cite as

Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino, and Hanna Sumita. Online Scheduling on Identical Machines with a Metric State Space. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goko_et_al:LIPIcs.STACS.2022.32,
  author =	{Goko, Hiromichi and Kawamura, Akitoshi and Kawase, Yasushi and Makino, Kazuhisa and Sumita, Hanna},
  title =	{{Online Scheduling on Identical Machines with a Metric State Space}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.32},
  URN =		{urn:nbn:de:0030-drops-158421},
  doi =		{10.4230/LIPIcs.STACS.2022.32},
  annote =	{Keywords: Online scheduling, Competitive analysis, Online dial-a-ride}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.28
Online Knapsack Problems with a Resource Buffer

Authors: Xin Han, Yasushi Kawase, Kazuhisa Makino, and Haruki Yokomaku

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
In this paper, we introduce online knapsack problems with a resource buffer. In the problems, we are given a knapsack with capacity 1, a buffer with capacity R >= 1, and items that arrive one by one. Each arriving item has to be taken into the buffer or discarded on its arrival irrevocably. When every item has arrived, we transfer a subset of items in the current buffer into the knapsack. Our goal is to maximize the total value of the items in the knapsack. We consider four variants depending on whether items in the buffer are removable (i.e., we can remove items in the buffer) or non-removable, and proportional (i.e., the value of each item is proportional to its size) or general. For the general&non-removable case, we observe that no constant competitive algorithm exists for any R >= 1. For the proportional&non-removable case, we show that a simple greedy algorithm is optimal for every R >= 1. For the general&removable and the proportional&removable cases, we present optimal algorithms for small R and give asymptotically nearly optimal algorithms for general R.
Cite as

Xin Han, Yasushi Kawase, Kazuhisa Makino, and Haruki Yokomaku. Online Knapsack Problems with a Resource Buffer. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{han_et_al:LIPIcs.ISAAC.2019.28,
  author =	{Han, Xin and Kawase, Yasushi and Makino, Kazuhisa and Yokomaku, Haruki},
  title =	{{Online Knapsack Problems with a Resource Buffer}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.28},
  URN =		{urn:nbn:de:0030-drops-115241},
  doi =		{10.4230/LIPIcs.ISAAC.2019.28},
  annote =	{Keywords: Online knapsack problem, Resource augmentation, Competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.51
Optimal Matroid Partitioning Problems

Authors: Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set E and k weighted matroids (E, \mathcal{I}_i, w_i), i = 1, \dots, k, and our task is to find a minimum partition (I_1,\dots,I_k) of E such that I_i \in \mathcal{I}_i for all i. For each objective function, we give a polynomial-time algorithm or prove NP-hardness. In particular, for the case when the given weighted matroids are identical and the objective function is the sum of the maximum weight in each set (i.e., \sum_{i=1}^k\max_{e\in I_i}w_i(e)), we show that the problem is strongly NP-hard but admits a PTAS.
Cite as

Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita. Optimal Matroid Partitioning Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ISAAC.2017.51,
  author =	{Kawase, Yasushi and Kimura, Kei and Makino, Kazuhisa and Sumita, Hanna},
  title =	{{Optimal Matroid Partitioning Problems}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{51:1--51:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.51},
  URN =		{urn:nbn:de:0030-drops-82712},
  doi =		{10.4230/LIPIcs.ISAAC.2017.51},
  annote =	{Keywords: Matroids, Partitioning problem, PTAS, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.32
Optimal Stopping Rules for Sequential Hypothesis Testing

Authors: Constantinos Daskalakis and Yasushi Kawase

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Suppose that we are given sample access to an unknown distribution p over n elements and an explicit distribution q over the same n elements. We would like to reject the null hypothesis "p=q" after seeing as few samples as possible, when p =/= q, while we never want to reject the null, when p=q. Well-known results show that Theta(sqrt{n}/epsilon^2) samples are necessary and sufficient for distinguishing whether p equals q versus p is epsilon-far from q in total variation distance. However, this requires the distinguishing radius epsilon to be fixed prior to deciding how many samples to request. Our goal is instead to design sequential hypothesis testers, i.e. online algorithms that request i.i.d. samples from p and stop as soon as they can confidently reject the hypothesis p=q, without being given a lower bound on the distance between p and q, when p =/= q. In particular, we want to minimize the number of samples requested by our tests as a function of the distance between p and q, and if p=q we want the algorithm, with high probability, to never reject the null. Our work is motivated by and addresses the practical challenge of sequential A/B testing in Statistics. We show that, when n=2, any sequential hypothesis test must see Omega(1/{d_{tv}(p,q)^2} log log 1/{d_{tv}(p,q)}) samples, with high (constant) probability, before it rejects p=q, where d_{tv}(p,q) is the - unknown to the tester - total variation distance between p and q. We match the dependence of this lower bound on d_{tv}(p,q) by proposing a sequential tester that rejects p=q from at most O({\sqrt{n}}/{d_{tv}(p,q)^2}log log 1/{d_{tv}(p,q)}) samples with high (constant) probability. The Omega(sqrt{n}) dependence on the support size n is also known to be necessary. We similarly provide two-sample sequential hypothesis testers, when sample access is given to both p and q, and discuss applications to sequential A/B testing.
Cite as

Constantinos Daskalakis and Yasushi Kawase. Optimal Stopping Rules for Sequential Hypothesis Testing. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{daskalakis_et_al:LIPIcs.ESA.2017.32,
  author =	{Daskalakis, Constantinos and Kawase, Yasushi},
  title =	{{Optimal Stopping Rules for Sequential Hypothesis Testing}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.32},
  URN =		{urn:nbn:de:0030-drops-78237},
  doi =		{10.4230/LIPIcs.ESA.2017.32},
  annote =	{Keywords: property testing, sequential hypothesis testing, A/B testing}
}
  • Refine by Type
  • 19 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 3 2024
  • 1 2022
  • 1 2019
  • Show More...

  • Refine by Author
  • 13 Kawase, Yasushi
  • 7 Makino, Kazuhisa
  • 4 Sumita, Hanna
  • 2 Gehnen, Matthias
  • 2 Miyauchi, Atsushi
  • Show More...

  • Refine by Series/Journal
  • 19 LIPIcs

  • Refine by Classification
  • 7 Theory of computation → Online algorithms
  • 3 Mathematics of computing → Combinatorial optimization
  • 2 Theory of computation → Algorithmic game theory
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Matroids and greedoids
  • Show More...

  • Refine by Keyword
  • 3 Competitive analysis
  • 2 Fair allocation
  • 2 NP-hardness
  • 2 Online scheduling
  • 2 competitive analysis
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact