3 Search Results for "Li, Jianqi"


Document
Parameterized Approximation Algorithms for TSP

Authors: Jianqi Zhou, Peihua Li, and Jiong Guo

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
We study the Traveling Salesman problem (TSP), where given a complete undirected graph G = (V,E) with n vertices and an edge cost function c:E↦R_{⩾0}, the goal is to find a minimum-cost cycle visiting every vertex exactly once. It is well-known that unless P = NP, TSP cannot be approximated in polynomial time within a factor of ρ(n) for any computable function ρ, while the metric case of TSP, that the edge cost function satisfies the △-inequality, admits a polynomial-time 1.5-approximation. We investigate TSP on general graphs from the perspective of parameterized approximability. A parameterized ρ-approximation algorithm returns a ρ-approximation solution in f(k)⋅|I|^O(1) time, where f is a computable function and k is a parameter of the input I. We introduce two parameters, which measure the distance of a given TSP-instance from the metric case, and achieve the following two results: - A 3-approximation algorithm for TSP in O((3k₁)! 8^k₁⋅ n²+n³) time, where k₁ is the number of triangles in which the edge costs violate the △-inequality. - A 3-approximation algorithm for TSP in O(n^O(k₂)) time and a (6k₂+9)-approximation algorithm for TSP in O(k₂^O(k₂)⋅n³) time, where k₂ is the minimum number of vertices, whose removal results in a metric graph. To our best knowledge, the above algorithms are the first non-trivial parameterized approximation algorithms for TSP on general graphs.

Cite as

Jianqi Zhou, Peihua Li, and Jiong Guo. Parameterized Approximation Algorithms for TSP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.ISAAC.2022.50,
  author =	{Zhou, Jianqi and Li, Peihua and Guo, Jiong},
  title =	{{Parameterized Approximation Algorithms for TSP}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{50:1--50:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.50},
  URN =		{urn:nbn:de:0030-drops-173358},
  doi =		{10.4230/LIPIcs.ISAAC.2022.50},
  annote =	{Keywords: FPT-approximation algorithms, the Traveling Salesman problem, the triangle inequality, fixed-parameter tractability, metric graphs}
}
Document
Termination of Dependently Typed Rewrite Rules

Authors: Jean-Pierre Jouannaud and Jianqi Li

Published in: LIPIcs, Volume 38, 13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015)


Abstract
Our interest is in automated termination proofs of higher-order rewrite rules in presence of dependent types modulo a theory T on base types. We first describe an original transformation to a type discipline without type dependencies which preserves non-termination. Since the user must reason on expressions of the transformed language, we then introduce an extension of the computability path ordering CPO for comparing dependently typed expressions named DCPO. Using the previous result, we show that DCPO is a well-founded order, behaving well in practice.

Cite as

Jean-Pierre Jouannaud and Jianqi Li. Termination of Dependently Typed Rewrite Rules. In 13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 38, pp. 257-272, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{jouannaud_et_al:LIPIcs.TLCA.2015.257,
  author =	{Jouannaud, Jean-Pierre and Li, Jianqi},
  title =	{{Termination of Dependently Typed Rewrite Rules}},
  booktitle =	{13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015)},
  pages =	{257--272},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-87-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{38},
  editor =	{Altenkirch, Thorsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TLCA.2015.257},
  URN =		{urn:nbn:de:0030-drops-51684},
  doi =		{10.4230/LIPIcs.TLCA.2015.257},
  annote =	{Keywords: rewriting, dependent types, strong normalization, path orderings}
}
Document
Church-Rosser Properties of Normal Rewriting

Authors: Jean-Pierre Jouannaud and Jianqi Li

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)


Abstract
We prove a general purpose abstract Church-Rosser result that captures most existing such results that rely on termination of computations. This is achieved by studying abstract normal rewriting in a way that allows to incorporate positions at the abstract level. New concrete Church-Rosser results are obtained, in particular for higher-order rewriting at higher types.

Cite as

Jean-Pierre Jouannaud and Jianqi Li. Church-Rosser Properties of Normal Rewriting. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 350-365, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{jouannaud_et_al:LIPIcs.CSL.2012.350,
  author =	{Jouannaud, Jean-Pierre and Li, Jianqi},
  title =	{{Church-Rosser Properties of Normal Rewriting}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{350--365},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.350},
  URN =		{urn:nbn:de:0030-drops-36839},
  doi =		{10.4230/LIPIcs.CSL.2012.350},
  annote =	{Keywords: abstract normal rewriting, Church-Rosser property}
}
  • Refine by Author
  • 2 Jouannaud, Jean-Pierre
  • 2 Li, Jianqi
  • 1 Guo, Jiong
  • 1 Li, Peihua
  • 1 Zhou, Jianqi

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Church-Rosser property
  • 1 FPT-approximation algorithms
  • 1 abstract normal rewriting
  • 1 dependent types
  • 1 fixed-parameter tractability
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2012
  • 1 2015
  • 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