3 Search Results for "Yanagisawa, Hiroki"

Document
DOI: 10.4230/LIPIcs.ITCS.2025.81
Online Balanced Allocation of Dynamic Components

Authors: Rajmohan Rajaraman and Omer Wasim

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We introduce Online Balanced Allocation of Dynamic Components (OBADC), a problem motivated by the practical challenge of dynamic resource allocation for large-scale distributed applications. In OBADC, we need to allocate a dynamic set of at most k𝓁 vertices (representing processes) in 𝓁 > 0 clusters. We consider an over-provisioned setup in which each cluster can hold at most k(1+ε) vertices, for an arbitrary constant ε > 0. The communication requirements among the vertices are modeled by the notion of a dynamically changing component, which is a subset of vertices that need to be co-located in the same cluster. At each time t, a request r_t of one of the following types arrives: 1) insertion of a vertex v forming a singleton component v at unit cost. 2) merge of (u,v) requiring that the components containing u and v be merged and co-located thereafter. 3) deletion of an existing vertex v at zero cost. Before serving any request, an algorithm can migrate vertices from one cluster to another, at a unit migration cost per vertex. We seek an online algorithm to minimize the total migration cost incurred for an arbitrary request sequence σ = (r_t)_{t > 0}, while simultaneously minimizing the number of clusters utilized. We analyze competitiveness with respect to an optimal clairvoyant offline algorithm with identical (over-provisioned) capacity constraints. We give an O(log k)-competitive algorithm for OBADC, and a matching lower-bound. The number of clusters utilized by our algorithm is always within a (2+ε) factor of the minimum. Furthermore, in a resource augmented setting where the optimal offline algorithm is constrained to capacity k per cluster, our algorithm obtains O(log k) competitiveness and utilizes a number of clusters within (1+ε) factor of the minimum. We also consider OBADC in the context of machine-learned predictions, where for each newly inserted vertex v at time t: i) with probability η > 0, the set of vertices (that exist at time t) in the component of v is revealed and, ii) with probability 1-η, no information is revealed. For OBADC with predictions, we give a O(1)-consistent and O(min(log 1/(η), log k))-robust algorithm.
Cite as

Rajmohan Rajaraman and Omer Wasim. Online Balanced Allocation of Dynamic Components. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 81:1-81:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rajaraman_et_al:LIPIcs.ITCS.2025.81,
  author =	{Rajaraman, Rajmohan and Wasim, Omer},
  title =	{{Online Balanced Allocation of Dynamic Components}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{81:1--81:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.81},
  URN =		{urn:nbn:de:0030-drops-227090},
  doi =		{10.4230/LIPIcs.ITCS.2025.81},
  annote =	{Keywords: online algorithms, competitive ratio, algorithms with predictions}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.9
Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists

Authors: Koki Hamada, Shuichi Miyazaki, and Hiroki Yanagisawa

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

Abstract
In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the well-known stable mechanisms is the man-oriented Gale-Shapley algorithm (MGS). MGS has a good property that it is strategy-proof to the men’s side, i.e., no man can obtain a better outcome by falsifying a preference list. We call such a mechanism a man-strategy-proof mechanism. Unfortunately, MGS is not a woman-strategy-proof mechanism. (Of course, if we flip the roles of men and women, we can see that the woman-oriented Gale-Shapley algorithm (WGS) is a woman-strategy-proof but not a man-strategy-proof mechanism.) Roth has shown that there is no stable mechanism that is simultaneously man-strategy-proof and woman-strategy-proof, which is known as Roth’s impossibility theorem. In this paper, we extend these results to the stable marriage problem with ties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth’s impossibility theorem takes over to SMTI. Therefore, we focus on the one-sided-strategy-proofness. In SMTI, one instance can have stable matchings of different sizes, and it is natural to consider the problem of finding a largest stable matching, known as MAX SMTI. Thus we incorporate the notion of approximation ratios used in the theory of approximation algorithms. We say that a stable-mechanism is a c-approximate-stable mechanism if it always returns a stable matching of size at least 1/c of a largest one. We also consider a restricted variant of MAX SMTI, which we call MAX SMTI-1TM, where only men’s lists can contain ties (and women’s lists must be strictly ordered). Our results are summarized as follows: (i) MAX SMTI admits both a man-strategy-proof 2-approximate-stable mechanism and a woman-strategy-proof 2-approximate-stable mechanism. (ii) MAX SMTI-1TM admits a woman-strategy-proof 2-approximate-stable mechanism. (iii) MAX SMTI-1TM admits a man-strategy-proof 1.5-approximate-stable mechanism. All these results are tight in terms of approximation ratios. Also, all these results apply for strategy-proofness against coalitions.
Cite as

Koki Hamada, Shuichi Miyazaki, and Hiroki Yanagisawa. Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hamada_et_al:LIPIcs.ISAAC.2019.9,
  author =	{Hamada, Koki and Miyazaki, Shuichi and Yanagisawa, Hiroki},
  title =	{{Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-115059},
  doi =		{10.4230/LIPIcs.ISAAC.2019.9},
  annote =	{Keywords: Stable marriage problem, strategy-proofness, approximation algorithm, ties, incomplete lists}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.361
A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties

Authors: Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear only in women's preference lists and (ii) each tie appears at the end of each woman's preference list. The current best lower bounds on the approximation ratio for this variant are 1.1052 unless P=NP and 1.25 under the unique games conjecture, while the current best upper bound is 1.4616. In this paper, we improve the upper bound to 1.25, which matches the lower bound under the unique games conjecture. Note that this is the first special case of the MAX SMTI where the tight approximation bound is obtained. The improved ratio is achieved via a new analysis technique, which avoids the complicated case-by-case analysis used in earlier studies. As a by-product of our analysis, we show that the integrality gap of natural IP and LP formulations for this variant is 1.25. We also show that the unrestricted MAX SMTI cannot be approximated with less than 1.5 unless the approximation ratio of a certain special case of the minimum maximal matching problem can be improved.
Cite as

Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa. A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 361-380, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2015.361,
  author =	{Huang, Chien-Chung and Iwama, Kazuo and Miyazaki, Shuichi and Yanagisawa, Hiroki},
  title =	{{A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{361--380},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.361},
  URN =		{urn:nbn:de:0030-drops-53123},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.361},
  annote =	{Keywords: stable marriage with ties and incomplete lists, approximation algorithm, integer program, linear program relaxation, integrality gap}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2019
  • 1 2015

  • Refine by Author
  • 2 Miyazaki, Shuichi
  • 2 Yanagisawa, Hiroki
  • 1 Hamada, Koki
  • 1 Huang, Chien-Chung
  • 1 Iwama, Kazuo
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 2 approximation algorithm
  • 1 Stable marriage problem
  • 1 algorithms with predictions
  • 1 competitive ratio
  • 1 incomplete lists
  • 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