Search Results

Documents authored by Li, Minming

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.44
Bayesian Calibrated Click-Through Auctions

Authors: Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo

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

Abstract
We study information design in click-through auctions, in which the bidders/advertisers bid for winning an opportunity to show their ads but only pay for realized clicks. The payment may or may not happen, and its probability is called the click-through rate (CTR). This auction format is widely used in the industry of online advertising. Bidders have private values, whereas the seller has private information about each bidder’s CTRs. We are interested in the seller’s problem of partially revealing CTR information to maximize revenue. Information design in click-through auctions turns out to be intriguingly different from almost all previous studies in this space since any revealed information about CTRs will never affect bidders' bidding behaviors - they will always bid their true value per click - but only affect the auction’s allocation and payment rule. In some sense, this makes information design effectively a constrained mechanism design problem. Our first result is an FPTAS to compute an approximately optimal mechanism under a constant number of bidders. The design of this algorithm leverages Bayesian bidder values which help to "smooth" the seller’s revenue function and lead to better tractability. The design of this FPTAS is complex and primarily algorithmic. Our second main result pursues the design of "simple" mechanisms that are approximately optimal yet more practical. We primarily focus on the two-bidder situation, which is already notoriously challenging as demonstrated in recent works. When bidders' CTR distribution is symmetric, we develop a simple prior-free signaling scheme, whose construction relies on a parameter termed optimal signal ratio. The constructed scheme provably obtains a good approximation as long as the maximum and minimum of bidders' value density functions do not differ much.
Cite as

Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo. Bayesian Calibrated Click-Through Auctions. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2024.44,
  author =	{Chen, Junjie and Li, Minming and Xu, Haifeng and Zuo, Song},
  title =	{{Bayesian Calibrated Click-Through Auctions}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{44:1--44:18},
  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.44},
  URN =		{urn:nbn:de:0030-drops-201878},
  doi =		{10.4230/LIPIcs.ICALP.2024.44},
  annote =	{Keywords: information design, ad auctions, online advertising, mechanism design}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.73
Dynamic Maximal Matching in Clique Networks

Authors: Minming Li, Peter Robinson, and Xianbin Zhu

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of n nodes is vertex-partitioned among k players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of 𝓁 edge insertions or deletions. We first show a lower bound of Ω((𝓁 log k)/(k²log n)) rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of Ω(𝓁/(klog n)) rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players. We also present a randomized algorithm that has an initialization time of O(n/(k log n)) rounds, while achieving an update time that that is independent of n: In more detail, the update time is O(⌈𝓁/k⌉ log k) against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes O (⌈𝓁/√k⌉ log k) rounds.
Cite as

Minming Li, Peter Robinson, and Xianbin Zhu. Dynamic Maximal Matching in Clique Networks. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 73:1-73:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2024.73,
  author =	{Li, Minming and Robinson, Peter and Zhu, Xianbin},
  title =	{{Dynamic Maximal Matching in Clique Networks}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{73:1--73:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.73},
  URN =		{urn:nbn:de:0030-drops-196017},
  doi =		{10.4230/LIPIcs.ITCS.2024.73},
  annote =	{Keywords: distributed graph algorithm, dynamic network, maximal matching, randomized algorithm, lower bound}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.38
Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings

Authors: Christoph Damerius, Peter Kling, Minming Li, Chenyang Xu, and Ruilong Zhang

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Scheduling with testing falls under the umbrella of the research on optimization with explorable uncertainty. In this model, each job has an upper limit on its processing time that can be decreased to a lower limit (possibly unknown) by some preliminary action (testing). Recently, [Christoph Dürr et al., 2020] has studied a setting where testing a job takes a unit time, and the goal is to minimize total completion time or makespan on a single machine. In this paper, we extend their problem to the budget setting in which each test consumes a job-specific cost, and we require that the total testing cost cannot exceed a given budget. We consider the offline variant (the lower processing time is known) and the oblivious variant (the lower processing time is unknown) and aim to minimize the total completion time or makespan on a single machine. For the total completion time objective, we show NP-hardness and derive a PTAS for the offline variant based on a novel LP rounding scheme. We give a (4+ε)-competitive algorithm for the oblivious variant based on a framework inspired by the worst-case lower-bound instance. For the makespan objective, we give an FPTAS for the offline variant and a (2+ε)-competitive algorithm for the oblivious variant. Our algorithms for the oblivious variants under both objectives run in time 𝒪(poly(n/ε)). Lastly, we show that our results are essentially optimal by providing matching lower bounds.
Cite as

Christoph Damerius, Peter Kling, Minming Li, Chenyang Xu, and Ruilong Zhang. Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{damerius_et_al:LIPIcs.ESA.2023.38,
  author =	{Damerius, Christoph and Kling, Peter and Li, Minming and Xu, Chenyang and Zhang, Ruilong},
  title =	{{Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.38},
  URN =		{urn:nbn:de:0030-drops-186915},
  doi =		{10.4230/LIPIcs.ESA.2023.38},
  annote =	{Keywords: scheduling, total completion time, makespan, LP rounding, competitive analysis, approximation algorithm, NP hardness, PTAS}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2020
LIPIcs, Volume 181, ISAAC 2020, Complete Volume

Authors: Yixin Cao, Siu-Wing Cheng, and Minming Li

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
LIPIcs, Volume 181, ISAAC 2020, Complete Volume
Cite as

31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 1-1012, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{cao_et_al:LIPIcs.ISAAC.2020,
  title =	{{LIPIcs, Volume 181, ISAAC 2020, Complete Volume}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{1--1012},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020},
  URN =		{urn:nbn:de:0030-drops-133439},
  doi =		{10.4230/LIPIcs.ISAAC.2020},
  annote =	{Keywords: LIPIcs, Volume 181, ISAAC 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Yixin Cao, Siu-Wing Cheng, and Minming Li

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ISAAC.2020.0,
  author =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.0},
  URN =		{urn:nbn:de:0030-drops-133448},
  doi =		{10.4230/LIPIcs.ISAAC.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.19
An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint

Authors: Gruia Calinescu, Florian Jaehn, Minming Li, and Kai Wang

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

Abstract
In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS).
Cite as

Gruia Calinescu, Florian Jaehn, Minming Li, and Kai Wang. An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{calinescu_et_al:LIPIcs.ISAAC.2017.19,
  author =	{Calinescu, Gruia and Jaehn, Florian and Li, Minming and Wang, Kai},
  title =	{{An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{19:1--19: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.19},
  URN =		{urn:nbn:de:0030-drops-82335},
  doi =		{10.4230/LIPIcs.ISAAC.2017.19},
  annote =	{Keywords: FPTAS, Scheduling, Approximation Algorithm}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact