7 Search Results for "Gong, Mingyang"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.49
Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents

Authors: Jiaxuan Ma, Yong Chen, Guangting Chen, Mingyang Gong, Guohui Lin, and An Zhang

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We study the fair allocation of indivisible items to n agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are only two different utility functions shared by the agents. We present a 2-approximation algorithm when the two utility functions are normalized, improving the previous best ratio of 16 √n shown for general normalized utility functions; thus this constant ratio approximation algorithm confirms the APX-completeness in this special case previously shown APX-hard. When there are only three agents, i.e., n = 3, the previous best ratio is 3 shown for general utility functions, and we present an improved and tight 5/3-approximation algorithm when the two utility functions are normalized, and a best possible and tight 2-approximation algorithm when the two utility functions are unnormalized.
Cite as

Jiaxuan Ma, Yong Chen, Guangting Chen, Mingyang Gong, Guohui Lin, and An Zhang. Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ma_et_al:LIPIcs.ISAAC.2025.49,
  author =	{Ma, Jiaxuan and Chen, Yong and Chen, Guangting and Gong, Mingyang and Lin, Guohui and Zhang, An},
  title =	{{Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.49},
  URN =		{urn:nbn:de:0030-drops-249570},
  doi =		{10.4230/LIPIcs.ISAAC.2025.49},
  annote =	{Keywords: Fair allocation, utilitarian social welfare, envy-free up to one item, envy-cycle elimination, round robin, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.3
Approximability of Longest Run Subsequence and Complementary Minimization Problems

Authors: Yuichi Asahiro, Mingyang Gong, Jesper Jansson, Guohui Lin, Sichen Lu, Eiji Miyano, Hirotaka Ono, Toshiki Saitoh, and Shunichi Tanaka

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
We study the polynomial-time approximability of the Longest Run Subsequence problem (LRS for short) and its complementary minimization variant Minimum Run Subsequence Deletion problem (MRSD for short). For a string S = s₁ ⋯ s_n over an alphabet Σ, a subsequence S' of S is S' = s_{i₁} ⋯ s_{i_p}, such that 1 ≤ i₁ < i₂ < … < i_p ≤ |S|. A run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S' of S is a subsequence of S in which every symbol σ ∈ Σ occurs in at most one run. The co-subsequence ̅{S'} of the subsequence S' = s_{i₁} ⋯ s_{i_p} in S is the subsequence obtained by deleting all the characters in S' from S, i.e., ̅{S'} = s_{j₁} ⋯ s_{j_{n-p}} such that j₁ < j₂ < … < j_{n-p} and {j₁, …, j_{n-p}} = {1, …, n}⧵ {i₁, …, i_p}. Given a string S, the goal of LRS (resp., MRSD) is to find a run subsequence S^* of S such that the length |S^*| is maximized (resp., the number | ̅{S^*}| of deleted symbols from S is minimized) over all the run subsequences of S. Let k be the maximum number of symbol occurrences in the input S. It is known that LRS and MRSD are APX-hard even if k = 2. In this paper, we show that LRS can be approximated in polynomial time within factors of (k+2)/3 for k = 2 or 3, and 2(k+1)/5 for every k ≥ 4. Furthermore, we show that MRSD can be approximated in linear time within a factor of (k+4)/4 if k is even and (k+3)/4 if k is odd.
Cite as

Yuichi Asahiro, Mingyang Gong, Jesper Jansson, Guohui Lin, Sichen Lu, Eiji Miyano, Hirotaka Ono, Toshiki Saitoh, and Shunichi Tanaka. Approximability of Longest Run Subsequence and Complementary Minimization Problems. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{asahiro_et_al:LIPIcs.WABI.2025.3,
  author =	{Asahiro, Yuichi and Gong, Mingyang and Jansson, Jesper and Lin, Guohui and Lu, Sichen and Miyano, Eiji and Ono, Hirotaka and Saitoh, Toshiki and Tanaka, Shunichi},
  title =	{{Approximability of Longest Run Subsequence and Complementary Minimization Problems}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.3},
  URN =		{urn:nbn:de:0030-drops-239290},
  doi =		{10.4230/LIPIcs.WABI.2025.3},
  annote =	{Keywords: Longest run subsequence, minimum run subsequence deletion, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.1
Representing Paths in Digraphs

Authors: Riccardo Dondi and Alexandru Popa

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
In this contribution we consider two combinatorial problems related to graph string matching, motivated by recent approaches in computational genomics. Given a DAG where each node is labeled by a symbol, the problems aim to find a path in the DAG whose nodes contain all (or the maximum number of) symbols of the alphabet. We introduce a decision problem, Σ-Representing Path, that asks whether there exists a path that contains all the symbols of the alphabet, and an optimization problem, called Maximum Representing Path, that asks for a path that contains the maximum number of symbols. We analyze the complexity of the problems, showing the NP-completeness of {Σ-Representing Path} when each symbol labels at most three nodes in the DAG, and showing the APX-hardness of Maximum Representing Path when each symbol labels at most two nodes in the DAG. We complement the first result by giving a polynomial-time algorithm for Σ-Representing Path when each symbol labels at most two nodes in the DAG. Then we investigate the parameterized complexity of the two problems when the DAG has a limited distance from a set of disjoint paths and we show that both problems are W[1]-hard for this parameter. We consider the approximation of Maximum Representing Path, giving an approximation algorithm of factor √OPT, where OPT is the value of an optimal solution of the problem. We also show that Maximum Representing Path cannot be approximated within factor e/(e-1) - α, for any constant α > 0, unless NP ⊆ DTIME(|V|^{O(log log |V|)}) (V is the set of nodes of the DAG).
Cite as

Riccardo Dondi and Alexandru Popa. Representing Paths in Digraphs. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dondi_et_al:LIPIcs.CPM.2025.1,
  author =	{Dondi, Riccardo and Popa, Alexandru},
  title =	{{Representing Paths in Digraphs}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{1:1--1:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.1},
  URN =		{urn:nbn:de:0030-drops-230954},
  doi =		{10.4230/LIPIcs.CPM.2025.1},
  annote =	{Keywords: Graph String Matching, Computational Complexity, Parameterized Complexity, Algorithms}
}
Document
Vision
DOI: 10.4230/TGDK.1.1.8
Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges

Authors: Claudia d'Amato, Louis Mahon, Pierre Monnin, and Giorgos Stamou

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
The graph model is nowadays largely adopted to model a wide range of knowledge and data, spanning from social networks to knowledge graphs (KGs), representing a successful paradigm of how symbolic and transparent AI can scale on the World Wide Web. However, due to their unprecedented volume, they are generally tackled by Machine Learning (ML) and mostly numeric based methods such as graph embedding models (KGE) and deep neural networks (DNNs). The latter methods have been proved lately very efficient, leading the current AI spring. In this vision paper, we introduce some of the main existing methods for combining KGs and ML, divided into two categories: those using ML to improve KGs, and those using KGs to improve results on ML tasks. From this introduction, we highlight research gaps and perspectives that we deem promising and currently under-explored for the involved research communities, spanning from KG support for LLM prompting, integration of KG semantics in ML models to symbol-based methods, interpretability of ML models, and the need for improved benchmark datasets. In our opinion, such perspectives are stepping stones in an ultimate view of KGs as central assets for neuro-symbolic and explainable AI.
Cite as

Claudia d'Amato, Louis Mahon, Pierre Monnin, and Giorgos Stamou. Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 8:1-8:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{damato_et_al:TGDK.1.1.8,
  author =	{d'Amato, Claudia and Mahon, Louis and Monnin, Pierre and Stamou, Giorgos},
  title =	{{Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{8:1--8:35},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.8},
  URN =		{urn:nbn:de:0030-drops-194824},
  doi =		{10.4230/TGDK.1.1.8},
  annote =	{Keywords: Graph-based Learning, Knowledge Graph Embeddings, Large Language Models, Explainable AI, Knowledge Graph Completion \& Curation}
}
Document
Position
DOI: 10.4230/TGDK.1.1.5
Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities

Authors: Jiaoyan Chen, Hang Dong, Janna Hastings, Ernesto Jiménez-Ruiz, Vanessa López, Pierre Monnin, Catia Pesquita, Petr Škoda, and Valentina Tamma

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
The term life sciences refers to the disciplines that study living organisms and life processes, and include chemistry, biology, medicine, and a range of other related disciplines. Research efforts in life sciences are heavily data-driven, as they produce and consume vast amounts of scientific data, much of which is intrinsically relational and graph-structured. The volume of data and the complexity of scientific concepts and relations referred to therein promote the application of advanced knowledge-driven technologies for managing and interpreting data, with the ultimate aim to advance scientific discovery. In this survey and position paper, we discuss recent developments and advances in the use of graph-based technologies in life sciences and set out a vision for how these technologies will impact these fields into the future. We focus on three broad topics: the construction and management of Knowledge Graphs (KGs), the use of KGs and associated technologies in the discovery of new knowledge, and the use of KGs in artificial intelligence applications to support explanations (explainable AI). We select a few exemplary use cases for each topic, discuss the challenges and open research questions within these topics, and conclude with a perspective and outlook that summarizes the overarching challenges and their potential solutions as a guide for future research.
Cite as

Jiaoyan Chen, Hang Dong, Janna Hastings, Ernesto Jiménez-Ruiz, Vanessa López, Pierre Monnin, Catia Pesquita, Petr Škoda, and Valentina Tamma. Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 5:1-5:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{chen_et_al:TGDK.1.1.5,
  author =	{Chen, Jiaoyan and Dong, Hang and Hastings, Janna and Jim\'{e}nez-Ruiz, Ernesto and L\'{o}pez, Vanessa and Monnin, Pierre and Pesquita, Catia and \v{S}koda, Petr and Tamma, Valentina},
  title =	{{Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:33},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.5},
  URN =		{urn:nbn:de:0030-drops-194791},
  doi =		{10.4230/TGDK.1.1.5},
  annote =	{Keywords: Knowledge graphs, Life science, Knowledge discovery, Explainable AI}
}
Document
DOI: 10.4230/LIPIcs.CPM.2023.2
Approximation Algorithms for the Longest Run Subsequence Problem

Authors: Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka

Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

Abstract
We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s_1 ⋯ s_n over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S' of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S^* of S such that the length |S^*| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time (k+1)/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 3/2 to 4/3.
Cite as

Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka. Approximation Algorithms for the Longest Run Subsequence Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{asahiro_et_al:LIPIcs.CPM.2023.2,
  author =	{Asahiro, Yuichi and Eto, Hiroshi and Gong, Mingyang and Jansson, Jesper and Lin, Guohui and Miyano, Eiji and Ono, Hirotaka and Tanaka, Shunichi},
  title =	{{Approximation Algorithms for the Longest Run Subsequence Problem}},
  booktitle =	{34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-276-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{259},
  editor =	{Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.2},
  URN =		{urn:nbn:de:0030-drops-179560},
  doi =		{10.4230/LIPIcs.CPM.2023.2},
  annote =	{Keywords: Longest run subsequence problem, bounded occurrence, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.53
Approximation Algorithms for Covering Vertices by Long Paths

Authors: Mingyang Gong, Jing Fan, Guohui Lin, and Eiji Miyano

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least k vertices is considered long. When k ≤ 3, the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4, the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O(1))-approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4. Both algorithms are based on local improvement, and their performance analyses are done via amortization.
Cite as

Mingyang Gong, Jing Fan, Guohui Lin, and Eiji Miyano. Approximation Algorithms for Covering Vertices by Long Paths. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gong_et_al:LIPIcs.MFCS.2022.53,
  author =	{Gong, Mingyang and Fan, Jing and Lin, Guohui and Miyano, Eiji},
  title =	{{Approximation Algorithms for Covering Vertices by Long Paths}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.53},
  URN =		{urn:nbn:de:0030-drops-168517},
  doi =		{10.4230/LIPIcs.MFCS.2022.53},
  annote =	{Keywords: Path cover, k-path, local improvement, amortized analysis, approximation algorithm}
}
  • Refine by Type
  • 7 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 3 2023
  • 1 2022

  • Refine by Author
  • 4 Gong, Mingyang
  • 4 Lin, Guohui
  • 3 Miyano, Eiji
  • 2 Asahiro, Yuichi
  • 2 Jansson, Jesper
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 2 TGDK

  • Refine by Classification
  • 4 Theory of computation → Design and analysis of algorithms
  • 1 Applied computing → Life and medical sciences
  • 1 Computing methodologies → Artificial intelligence
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Information systems → Graph-based database models
  • Show More...

  • Refine by Keyword
  • 4 approximation algorithm
  • 2 Explainable AI
  • 1 Algorithms
  • 1 Computational Complexity
  • 1 Fair allocation
  • 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