16 Search Results for "Wang, Yuyi"

Artifact
Software
DOI: 10.4230/artifacts.25483
l2l7l9p/Polynomials-for-WFOMC

Authors: Qipeng Kuang

Abstract
Cite as

Qipeng Kuang. l2l7l9p/Polynomials-for-WFOMC (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25483,
   title = {{l2l7l9p/Polynomials-for-WFOMC}}, 
   author = {Kuang, Qipeng},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:e82fa8e26998cfb9e25e723b2c1182f17a82276e;origin=https://github.com/l2l7l9p/Polynomials-for-WFOMC;visit=swh:1:snp:c93a1d1b89d04f98bc8bac6988a75fd140eb9ad0;anchor=swh:1:rev:e474a633cb4a55ef35e7aaf70df4d765cfbef02d}{\texttt{swh:1:dir:e82fa8e26998cfb9e25e723b2c1182f17a82276e}} (visited on 2026-02-18)},
   url = {https://github.com/l2l7l9p/Polynomials-for-WFOMC},
   doi = {10.4230/artifacts.25483},
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.7
Bridging Weighted First Order Model Counting and Graph Polynomials

Authors: Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. It can be solved in time polynomial in the domain size for sentences from the two-variable fragment with counting quantifiers, known as C^2. This polynomial-time complexity is known to be retained when extending C^2 by one of the following axioms: linear order axiom, tree axiom, forest axiom, directed acyclic graph axiom or connectedness axiom. An interesting question remains as to which other axioms can be added to the first-order sentences in this way. We provide a new perspective on this problem by associating WFOMC with graph polynomials. Using WFOMC, we define Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. It turns out that these polynomials have the following interesting properties. First, they can be computed in polynomial time in the domain size for sentences from C^2. Second, we can use them to solve WFOMC with all of the existing axioms known to be tractable as well as with new ones such as bipartiteness, strong connectedness, having k connected components, etc. Third, the well-known Tutte polynomial can be recovered as a special case of the Weak Connectedness Polynomial, and the Strict and Non-Strict Directed Chromatic Polynomials can be recovered from the Strong Connectedness Polynomials.
Cite as

Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang. Bridging Weighted First Order Model Counting and Graph Polynomials. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kuang_et_al:LIPIcs.CSL.2026.7,
  author =	{Kuang, Qipeng and Ku\v{z}elka, Ond\v{r}ej and Wang, Yuanhong and Wang, Yuyi},
  title =	{{Bridging Weighted First Order Model Counting and Graph Polynomials}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.7},
  URN =		{urn:nbn:de:0030-drops-254316},
  doi =		{10.4230/LIPIcs.CSL.2026.7},
  annote =	{Keywords: Weighted First-Order Model Counting, Axiom, Enumerative Combinatorics, Tutte Polynomial}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.45
Fairness in the k-Server Problem

Authors: Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, and Cameron Musco

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We initiate a formal study of fairness for the k-server problem, where the objective is not only to minimize the total movement cost, but also to distribute the cost equitably among servers. We first define a general notion of (α,β)-fairness, where, for parameters α ≥ 1 and β ≥ 0, no server incurs more than an α/k-fraction of the total cost plus an additive term β. We then show that fairness can be achieved without a loss in competitiveness in both the offline and online settings. In the offline setting, we give a deterministic algorithm that, for any ε > 0, transforms any optimal solution into an (α,β)-fair solution for α = 1 + ε and β = O(diam ⋅ log k / ε), while increasing the cost of the solution by just an additive O(diam ⋅ k log k / ε) term. Here diam is the diameter of the underlying metric space. We give a similar result in the online setting, showing that any competitive algorithm can be transformed into a randomized online algorithm that is fair with high probability against an oblivious adversary and still competitive up to a small loss. The above results leave open a significant question: can fairness be achieved in the online setting, either with a deterministic algorithm or a randomized algorithm, against a fully adaptive adversary? We make progress towards answering this question, showing that the classic deterministic Double Coverage Algorithm (DCA) is fair on line metrics and on tree metrics when k = 2. However, we also show a negative result: DCA fails to be fair for any non-vacuous parameters on general tree metrics. We further show that on uniform metrics (i.e., the paging problem), the deterministic First-In First-Out (FIFO) algorithm is fair. We show that any "marking algorithm", including the Least Recently Used (LRU) algorithm, also satisfies a weaker, but still meaningful notion of fairness.
Cite as

Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, and Cameron Musco. Fairness in the k-Server Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{daneshvaramoli_et_al:LIPIcs.ITCS.2026.45,
  author =	{Daneshvaramoli, Mohammadreza and Hajiesmaili, Mohammad and Kamali, Shahin and Karisani, Helia and Musco, Cameron},
  title =	{{Fairness in the k-Server Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{45:1--45:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.45},
  URN =		{urn:nbn:de:0030-drops-253328},
  doi =		{10.4230/LIPIcs.ITCS.2026.45},
  annote =	{Keywords: k-server problem, online algorithms, fairness, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.94
Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Authors: Yingxi Li, Ellen Vitercik, and Mingwei Yang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In the online metric matching problem, n servers and n requests lie in a metric space. Servers are available upfront, and requests arrive sequentially. An arriving request must be matched immediately and irrevocably to an available server, incurring a cost equal to their distance. The goal is to minimize the total matching cost. We study this problem in [0, 1]^d with the Euclidean metric, when servers are adversarial and requests are independently drawn from distinct distributions that satisfy a mild smoothness condition. Our main result is an O(1)-competitive algorithm for d ≠ 2 that requires no distributional knowledge, relying only on a single sample from each request distribution. To our knowledge, this is the first algorithm to achieve an o(log n) competitive ratio for non-trivial metrics beyond the i.i.d. setting. Our approach bypasses the Ω(log n) barrier introduced by probabilistic metric embeddings: instead of analyzing the embedding distortion and the algorithm separately, we directly bound the cost of the algorithm on the target metric space of a simple deterministic embedding. We then combine this analysis with lower bounds on the offline optimum for Euclidean metrics, derived via majorization arguments, to obtain our guarantees.
Cite as

Yingxi Li, Ellen Vitercik, and Mingwei Yang. Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 94:1-94:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2026.94,
  author =	{Li, Yingxi and Vitercik, Ellen and Yang, Mingwei},
  title =	{{Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{94:1--94:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.94},
  URN =		{urn:nbn:de:0030-drops-253815},
  doi =		{10.4230/LIPIcs.ITCS.2026.94},
  annote =	{Keywords: Online algorithm, Metric matching, Competitive analysis, Smoothed analysis}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.23
Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection

Authors: Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle Yeo

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over p parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the p cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an 𝒪(p) approximation algorithm for the problem with p parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to 𝒪(√p). We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network.
Cite as

Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle Yeo. Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.DISC.2025.23,
  author =	{Chatterjee, Krishnendu and K\v{r}i\v{s}\v{t}an, Jan Maty\'{a}\v{s} and Schmid, Stefan and Svoboda, Jakub and Yeo, Michelle},
  title =	{{Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.23},
  URN =		{urn:nbn:de:0030-drops-248402},
  doi =		{10.4230/LIPIcs.DISC.2025.23},
  annote =	{Keywords: Blockchains, Cryptocurrencies, Payment Channel Networks, Throughput, Optimisation, Graph Algorithms, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.24
Validity in Network-Agnostic Byzantine Agreement

Authors: Andrei Constantinescu, Marc Dufay, Diana Ghinea, and Roger Wattenhofer

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Byzantine Agreement (BA) considers a setting of n parties, out of which up to t can exhibit byzantine (malicious) behavior. Honest parties must decide on a common value (agreement), which must belong to a set determined by the honest inputs (validity). Depending on the use case, this set can grow or shrink, leading to various possible desiderata collectively known as validity conditions. Varying the validity property requirement can affect the regime under which BA is solvable. Our work investigates how the selected validity property impacts BA solvability in the network-agnostic model, where the network can either be synchronous with up to t_s byzantine parties or asynchronous with up to t_a ≤ t_s byzantine parties. We give necessary and sufficient conditions for a validity property to render BA solvable, both for the case with cryptographic setup and for the one without. This traces the precise boundary of solvability in the network-agnostic model for every validity property. Our proof of sufficiency provides a universal protocol, that achieves BA for a given validity property whenever the provided conditions are satisfied. We note that, for any non-trivial validity property, the condition 2 ⋅ t_s + t_a < n is necessary for BA to be solvable, even with cryptographic setup. Specializing this claim to t_a = 0 gives that t < n / 2 is required whenever one expects a purely synchronous protocol to also work in an asynchronous network when there are no corruptions. This is especially surprising given that, for some validity properties, t < n is a sufficient condition without the last stipulation.
Cite as

Andrei Constantinescu, Marc Dufay, Diana Ghinea, and Roger Wattenhofer. Validity in Network-Agnostic Byzantine Agreement. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{constantinescu_et_al:LIPIcs.DISC.2025.24,
  author =	{Constantinescu, Andrei and Dufay, Marc and Ghinea, Diana and Wattenhofer, Roger},
  title =	{{Validity in Network-Agnostic Byzantine Agreement}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.24},
  URN =		{urn:nbn:de:0030-drops-248413},
  doi =		{10.4230/LIPIcs.DISC.2025.24},
  annote =	{Keywords: byzantine agreement, validity, network-agnostic protocols}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.15
Beyond Optimal Fault-Tolerance

Authors: Andrew Lewis-Pye and Tim Roughgarden

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
One of the most basic properties of a consensus protocol is its fault-tolerance - the maximum fraction of faulty participants that the protocol can tolerate without losing fundamental guarantees such as safety and liveness. Because of its importance, the optimal fault-tolerance achievable by any protocol has been characterized in a wide range of settings. For example, for state machine replication (SMR) protocols operating in the partially synchronous setting, it is possible to simultaneously guarantee consistency against α-bounded adversaries (i.e., adversaries that control less than an α fraction of the participants) and liveness against β-bounded adversaries if and only if α + 2β ≤ 1. This paper characterizes to what extent "better-than-optimal" fault-tolerance guarantees are possible for SMR protocols when the standard consistency requirement is relaxed to allow a bounded number r of consistency violations, each potentially leading to the rollback of recently finalized transactions. We prove that bounded rollback is impossible without additional timing assumptions and investigate protocols that tolerate and recover from consistency violations whenever message delays around the time of an attack are bounded by a parameter Δ^* (which may be arbitrarily larger than the parameter Δ that bounds post-GST message delays in the partially synchronous model). Here, a protocol’s fault-tolerance can be a non-constant function of r, and we prove, for each r, matching upper and lower bounds on the optimal "recoverable fault-tolerance" achievable by any SMR protocol. For example, for protocols that guarantee liveness against 1/3-bounded adversaries in the partially synchronous setting, a 5/9-bounded adversary can always cause one consistency violation but not two, and a 2/3-bounded adversary can always cause two consistency violations but not three. Our positive results are achieved through a generic "recovery procedure" that can be grafted on to any accountable SMR protocol and restores consistency following a violation while rolling back only transactions that were finalized in the previous 2Δ^* timesteps.
Cite as

Andrew Lewis-Pye and Tim Roughgarden. Beyond Optimal Fault-Tolerance. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lewispye_et_al:LIPIcs.AFT.2025.15,
  author =	{Lewis-Pye, Andrew and Roughgarden, Tim},
  title =	{{Beyond Optimal Fault-Tolerance}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{15:1--15:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.15},
  URN =		{urn:nbn:de:0030-drops-247341},
  doi =		{10.4230/LIPIcs.AFT.2025.15},
  annote =	{Keywords: Distributed computing, consensus, recovery}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.18
Towards Practical First-Order Model Counting

Authors: Ananth K. Kidambi, Guramrit Singh, Paulius Dilkas, and Kuldeep S. Meel

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
First-order model counting (FOMC) is the problem of counting the number of models of a sentence in first-order logic. Since lifted inference techniques rely on reductions to variants of FOMC, the design of scalable methods for FOMC has attracted attention from both theoreticians and practitioners over the past decade. Recently, a new approach based on first-order knowledge compilation was proposed. This approach, called Crane, instead of simply providing the final count, generates definitions of (possibly recursive) functions that can be evaluated with different arguments to compute the model count for any domain size. However, this approach is not fully automated, as it requires manual evaluation of the constructed functions. The primary contribution of this work is a fully automated compilation algorithm, called Crane2, which transforms the function definitions into C++ code equipped with arbitrary-precision arithmetic. These additions allow the new FOMC algorithm to scale to domain sizes over 500,000 times larger than the current state of the art, as demonstrated through experimental results.
Cite as

Ananth K. Kidambi, Guramrit Singh, Paulius Dilkas, and Kuldeep S. Meel. Towards Practical First-Order Model Counting. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kidambi_et_al:LIPIcs.SAT.2025.18,
  author =	{Kidambi, Ananth K. and Singh, Guramrit and Dilkas, Paulius and Meel, Kuldeep S.},
  title =	{{Towards Practical First-Order Model Counting}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.18},
  URN =		{urn:nbn:de:0030-drops-237527},
  doi =		{10.4230/LIPIcs.SAT.2025.18},
  annote =	{Keywords: First-order model counting, knowledge compilation, lifted inference}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.74
Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay

Authors: Noam Touitou

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

Abstract
We consider the online service with delay problem, in which a server traverses a metric space to serve requests that arrive over time. Requests gather individual delay cost while awaiting service, penalizing service latency; an algorithm seeks to minimize both its movement cost and the total delay cost. Algorithms for the problem (on general metric spaces) are only known for the clairvoyant model, where the algorithm knows future delay cost in advance (e.g., Azar et al., STOC'17; Azar and Touitou, FOCS'19; Touitou, STOC'23). However, in the non-clairvoyant setting, only negative results are known: where n is the size of the metric space and m is the number of requests, there are lower bounds of Ω(√n) and Ω(√m) on competitiveness (Azar et al., STOC'17), that hold even for randomized algorithms (Le et al., SODA'23). In this paper, we present the first algorithm for non-clairvoyant online service with delay. Our algorithm is deterministic and O(min{√n log n, √m log m})-competitive; combined with the lower bounds of Azar et al., this settles the correct competitive ratio for the problem up to logarithmic factors, in terms of both n and m.
Cite as

Noam Touitou. Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 74:1-74:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{touitou:LIPIcs.STACS.2025.74,
  author =	{Touitou, Noam},
  title =	{{Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{74:1--74:21},
  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.74},
  URN =		{urn:nbn:de:0030-drops-228995},
  doi =		{10.4230/LIPIcs.STACS.2025.74},
  annote =	{Keywords: Online, Delay, Deadlines, k-server, Non-clairvoyant}
}
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.45
A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems

Authors: Qian Li, Minghui Ouyang, and Yuyi Wang

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

Abstract
This paper presents a distributed algorithm in the CONGEST model that achieves a (1+ε)-approximation for row-sparse fractional covering problems (RS-FCP) and the dual column-sparse fraction packing problems (CS-FPP). Compared with the best-known (1+ε)-approximation CONGEST algorithm for RS-FCP/CS-FPP developed by Kuhn, Moscibroda, and Wattenhofer (SODA'06), our algorithm is not only much simpler but also significantly improves the dependency on ε.
Cite as

Qian Li, Minghui Ouyang, and Yuyi Wang. A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 45:1-45:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ISAAC.2024.45,
  author =	{Li, Qian and Ouyang, Minghui and Wang, Yuyi},
  title =	{{A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{45:1--45:8},
  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.45},
  URN =		{urn:nbn:de:0030-drops-221726},
  doi =		{10.4230/LIPIcs.ISAAC.2024.45},
  annote =	{Keywords: CONGEST model, row-sparse fractional covering, column-sparse fractional packing, positive linear programming, simple algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2022.5
Linear Programs with Conjunctive Queries

Authors: Florent Capelli, Nicolas Crosetti, Joachim Niehren, and Jan Ramon

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
In this paper, we study the problem of optimizing a linear program whose variables are the answers to a conjunctive query. For this we propose the language LP(CQ) for specifying linear programs whose constraints and objective functions depend on the answer sets of conjunctive queries. We contribute an efficient algorithm for solving programs in a fragment of LP(CQ). The naive approach constructs a linear program having as many variables as there are elements in the answer set of the queries. Our approach constructs a linear program having the same optimal value but fewer variables. This is done by exploiting the structure of the conjunctive queries using generalized hypertree decompositions of small width to factorize elements of the answer set together. We illustrate the various applications of LP(CQ) programs on three examples: optimizing deliveries of resources, minimizing noise for differential privacy, and computing the s-measure of patterns in graphs as needed for data mining.
Cite as

Florent Capelli, Nicolas Crosetti, Joachim Niehren, and Jan Ramon. Linear Programs with Conjunctive Queries. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{capelli_et_al:LIPIcs.ICDT.2022.5,
  author =	{Capelli, Florent and Crosetti, Nicolas and Niehren, Joachim and Ramon, Jan},
  title =	{{Linear Programs with Conjunctive Queries}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.5},
  URN =		{urn:nbn:de:0030-drops-158796},
  doi =		{10.4230/LIPIcs.ICDT.2022.5},
  annote =	{Keywords: Database queries, linear programming, hypergraph decomposition}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.61
The k-Server Problem with Delays on the Uniform Metric Space

Authors: Predrag Krnetić, Darya Melnyk, Yuyi Wang, and Roger Wattenhofer

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

Abstract
In this paper, we present tight bounds for the k-server problem with delays in the uniform metric space. The problem is defined on n+k nodes in the uniform metric space which can issue requests over time. These requests can be served directly or with some delay using k servers, by moving a server to the corresponding node with an open request. The task is to find an online algorithm that can serve the requests while minimizing the total moving and delay costs. We first provide a lower bound by showing that the competitive ratio of any deterministic online algorithm cannot be better than (2k+1) in the clairvoyant setting. We will then show that conservative algorithms (without delay) can be equipped with an accumulative delay function such that all such algorithms become (2k+1)-competitive in the non-clairvoyant setting. Together, the two bounds establish a tight result for both, the clairvoyant and the non-clairvoyant settings.
Cite as

Predrag Krnetić, Darya Melnyk, Yuyi Wang, and Roger Wattenhofer. The k-Server Problem with Delays on the Uniform Metric Space. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{krnetic_et_al:LIPIcs.ISAAC.2020.61,
  author =	{Krneti\'{c}, Predrag and Melnyk, Darya and Wang, Yuyi and Wattenhofer, Roger},
  title =	{{The k-Server Problem with Delays on the Uniform Metric Space}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{61:1--61:13},
  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.61},
  URN =		{urn:nbn:de:0030-drops-134056},
  doi =		{10.4230/LIPIcs.ISAAC.2020.61},
  annote =	{Keywords: Online k-Server, Paging, Delayed Service, Conservative Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.16
Algorithmic Channel Design

Authors: Georgia Avarikioti, Yuyi Wang, and Roger Wattenhofer

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Payment networks, also known as channels, are a most promising solution to the throughput problem of cryptocurrencies. In this paper we study the design of capital-efficient payment networks, offline as well as online variants. We want to know how to compute an efficient payment network topology, how capital should be assigned to the individual edges, and how to decide which transactions to accept. Towards this end, we present a flurry of interesting results, basic but generally applicable insights on the one hand, and hardness results and approximation algorithms on the other hand.
Cite as

Georgia Avarikioti, Yuyi Wang, and Roger Wattenhofer. Algorithmic Channel Design. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{avarikioti_et_al:LIPIcs.ISAAC.2018.16,
  author =	{Avarikioti, Georgia and Wang, Yuyi and Wattenhofer, Roger},
  title =	{{Algorithmic Channel Design}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.16},
  URN =		{urn:nbn:de:0030-drops-99648},
  doi =		{10.4230/LIPIcs.ISAAC.2018.16},
  annote =	{Keywords: blockchain, payment channels, layer 2 solution, network design, payment hubs, routing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.62
Impatient Online Matching

Authors: Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We investigate the problem of Min-cost Perfect Matching with Delays (MPMD) in which requests are pairwise matched in an online fashion with the objective to minimize the sum of space cost and time cost. Though linear-MPMD (i.e., time cost is linear in delay) has been thoroughly studied in the literature, it does not well model impatient requests that are common in practice. Thus, we propose convex-MPMD where time cost functions are convex, capturing the situation where time cost increases faster and faster. Since the existing algorithms for linear-MPMD are not competitive any more, we devise a new deterministic algorithm for convex-MPMD problems. For a large class of convex time cost functions, our algorithm achieves a competitive ratio of O(k) on any k-point uniform metric space. Moreover, our deterministic algorithm is asymptotically optimal, which uncover a substantial difference between convex-MPMD and linear-MPMD which allows a deterministic algorithm with constant competitive ratio on any uniform metric space.
Cite as

Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer. Impatient Online Matching. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 62:1-62:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ISAAC.2018.62,
  author =	{Liu, Xingwu and Pan, Zhida and Wang, Yuyi and Wattenhofer, Roger},
  title =	{{Impatient Online Matching}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{62:1--62:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.62},
  URN =		{urn:nbn:de:0030-drops-100107},
  doi =		{10.4230/LIPIcs.ISAAC.2018.62},
  annote =	{Keywords: online algorithm, online matching, convex function, competitive analysis, lower bound}
}
  • Refine by Type
  • 15 Document/PDF
  • 9 Document/HTML
  • 1 Artifact

  • Refine by Publication Year
  • 4 2026
  • 6 2025
  • 1 2024
  • 1 2022
  • 1 2020
  • Show More...

  • Refine by Author
  • 6 Wang, Yuyi
  • 5 Wattenhofer, Roger
  • 2 Kuang, Qipeng
  • 1 Ashlagi, Itai
  • 1 Avarikioti, Georgia
  • Show More...

  • Refine by Series/Journal
  • 15 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Online algorithms
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → K-server algorithms
  • 1 Mathematics of computing → Combinatorics
  • Show More...

  • Refine by Keyword
  • 4 competitive analysis
  • 1 Approximation Algorithms
  • 1 Axiom
  • 1 Blockchains
  • 1 CONGEST model
  • 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