2 Search Results for "Han, Jie"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.64
The Decision Problem for Perfect Matchings in Dense Hypergraphs

Authors: Luyining Gan and Jie Han

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Given 1 ≤ 𝓁 < k and δ ≥ 0, let PM(k,𝓁,δ) be the decision problem for the existence of perfect matchings in n-vertex k-uniform hypergraphs with minimum 𝓁-degree at least δ binom(n-𝓁,k-𝓁). For k ≥ 3, the decision problem in general k-uniform hypergraphs, equivalently PM(k,𝓁,0), is one of Karp’s 21 NP-complete problems. Moreover, for k ≥ 3, a reduction of Szymańska showed that PM(k, 𝓁, δ) is NP-complete for δ < 1-(1-1/k)^{k-𝓁}. A breakthrough by Keevash, Knox and Mycroft [STOC '13] resolved this problem for 𝓁 = k-1 by showing that PM(k, k-1, δ) is in P for δ > 1/k. Based on their result for 𝓁 = k-1, Keevash, Knox and Mycroft conjectured that PM(k, 𝓁, δ) is in P for every δ > 1-(1-1/k)^{k-𝓁}. In this paper it is shown that this decision problem for perfect matchings can be reduced to the study of the minimum 𝓁-degree condition forcing the existence of fractional perfect matchings. That is, we hopefully solve the "computational complexity" aspect of the problem by reducing it to a well-known extremal problem in hypergraph theory. In particular, together with existing results on fractional perfect matchings, this solves the conjecture of Keevash, Knox and Mycroft for 𝓁 ≥ 0.4k.
Cite as

Luyining Gan and Jie Han. The Decision Problem for Perfect Matchings in Dense Hypergraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 64:1-64:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gan_et_al:LIPIcs.ICALP.2022.64,
  author =	{Gan, Luyining and Han, Jie},
  title =	{{The Decision Problem for Perfect Matchings in Dense Hypergraphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.64},
  URN =		{urn:nbn:de:0030-drops-164057},
  doi =		{10.4230/LIPIcs.ICALP.2022.64},
  annote =	{Keywords: Computational Complexity, Perfect Matching, Hypergraph}
}
Document
DOI: 10.4230/LITES-v004-i001-a002
Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results

Authors: Florian Kluge

Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1

Abstract
The concept of a firm real-time task implies the notion of a firm deadline that should not be missed by the jobs of this task. If a deadline miss occurs, the concerned job yields no value to the system. For some applications domains, this restrictive notion can be relaxed. For example, robust control systems can tolerate that single executions of a control loop miss their deadlines, and still yield an acceptable behaviour. Thus, systems can be developed under more optimistic assumptions, e.g. by allowing overloads. However, care must be taken that deadline misses do not accumulate. This restriction can be expressed by the model of (m,k)-firm real-time tasks that require that from any k consecutive jobs at least m are executed successfully. In this article, we extend our prior work on the MKU scheduling heuristic. MKU uses history-cognisant utility functions as means for making decisions in overload situations. We present new theoretical results on MKU and on other schedulers for (m,k)-firm real-time tasks. Based on extensive simulations, we assess the performance of these schedulers. The results allow us to identify task set characteristics that can be used as guidelines for choosing a scheduler for a concrete use case.
Cite as

Florian Kluge. Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 02:1-02:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{kluge:LITES-v004-i001-a002,
  author =	{Kluge, Florian},
  title =	{{Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:25},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a002},
  doi =		{10.4230/LITES-v004-i001-a002},
  annote =	{Keywords: Real-time Scheduling, (m, k)-Firm Real-Time Tasks}
}
  • Refine by Author
  • 1 Gan, Luyining
  • 1 Han, Jie
  • 1 Kluge, Florian

  • Refine by Classification
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 (m
  • 1 Computational Complexity
  • 1 Hypergraph
  • 1 Perfect Matching
  • 1 Real-time Scheduling
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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