4 Search Results for "Zhu, Jasper"

Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.38
PACE Solver Description: HitS&DoSeS - Exact and Heuristic Solvers for the Dominating Set and Hitting Set Problems

Authors: Sylwester Swat

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
This article briefly describes the most important algorithms and techniques used in HitS&DoSeS, a dominating set and hitting set solver submitted to the PACE 2025 contest (10th Parameterized Algorithms and Computational Experiments Challenge). Used approaches for the exact and heuristic tracks are described, for both the dominating set and the hitting set problems.
Cite as

Sylwester Swat. PACE Solver Description: HitS&DoSeS - Exact and Heuristic Solvers for the Dominating Set and Hitting Set Problems. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 38:1-38:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{swat:LIPIcs.IPEC.2025.38,
  author =	{Swat, Sylwester},
  title =	{{PACE Solver Description: HitS\&DoSeS - Exact and Heuristic Solvers for the Dominating Set and Hitting Set Problems}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{38:1--38:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.38},
  URN =		{urn:nbn:de:0030-drops-251705},
  doi =		{10.4230/LIPIcs.IPEC.2025.38},
  annote =	{Keywords: dominating set, hitting set, exact algorithms, heuristic algorithms, large graphs, combinatorial optimization}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.17
Core-Guided Linear Programming-Based Maximum Satisfiability

Authors: George Katsirelos

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

Abstract
The core-guided algorithm OLL is the basis of some of the most successful algorithms for MaxSAT in recent evaluations. It works by iteratively finding cores of the formula and transforming it so that it exhibits a higher lower bound. It has recently been shown to implicitly discover cores of the original formula, as well as a compact representation of its reasoning within a linear program. In this paper, we use and extend these results to design a practical MaxSAT solver. We show an explicit linear program which matches and usually exceeds the bound computed by OLL. We show that OLL can be restated as an algorithm that explicitly computes a feasible dual solution of this linear program. This restated algorithm naturally works with an arbitrary dual solution. It can in fact be used to improve any LP representation of the MaxSAT instance. This presents a large increase of the potential design space for such algorithms. We describe some potential improvements from this insight and show that an implementation outperforms the state of the art algorithms on the set of instances from the latest MaxSAT evaluation.
Cite as

George Katsirelos. Core-Guided Linear Programming-Based Maximum Satisfiability. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{katsirelos:LIPIcs.SAT.2025.17,
  author =	{Katsirelos, George},
  title =	{{Core-Guided Linear Programming-Based Maximum Satisfiability}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{17:1--17:17},
  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.17},
  URN =		{urn:nbn:de:0030-drops-237513},
  doi =		{10.4230/LIPIcs.SAT.2025.17},
  annote =	{Keywords: maximum satisfiability, core-guided solvers, linear programming}
}
Document
Vision
DOI: 10.4230/TGDK.1.1.3
Knowledge Engineering Using Large Language Models

Authors: Bradley P. Allen, Lise Stork, and Paul Groth

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
Knowledge engineering is a discipline that focuses on the creation and maintenance of processes that generate and apply knowledge. Traditionally, knowledge engineering approaches have focused on knowledge expressed in formal languages. The emergence of large language models and their capabilities to effectively work with natural language, in its broadest sense, raises questions about the foundations and practice of knowledge engineering. Here, we outline the potential role of LLMs in knowledge engineering, identifying two central directions: 1) creating hybrid neuro-symbolic knowledge systems; and 2) enabling knowledge engineering in natural language. Additionally, we formulate key open research questions to tackle these directions.
Cite as

Bradley P. Allen, Lise Stork, and Paul Groth. Knowledge Engineering Using Large Language Models. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{allen_et_al:TGDK.1.1.3,
  author =	{Allen, Bradley P. and Stork, Lise and Groth, Paul},
  title =	{{Knowledge Engineering Using Large Language Models}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:19},
  ISSN =	{2942-7517},
  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.3},
  URN =		{urn:nbn:de:0030-drops-194777},
  doi =		{10.4230/TGDK.1.1.3},
  annote =	{Keywords: knowledge engineering, large language models}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.38
An Improved Approximation Algorithm for the Matching Augmentation Problem

Authors: Joseph Cheriyan, Robert Cummings, Jack Dippel, and Jasper Zhu

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We present a 5/3-approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. A 7/4-approximation algorithm for the same problem was presented recently, see Cheriyan, et al., "The matching augmentation problem: a 7/4-approximation algorithm," Math. Program., 182(1):315-354, 2020. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems.
Cite as

Joseph Cheriyan, Robert Cummings, Jack Dippel, and Jasper Zhu. An Improved Approximation Algorithm for the Matching Augmentation Problem. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cheriyan_et_al:LIPIcs.ISAAC.2021.38,
  author =	{Cheriyan, Joseph and Cummings, Robert and Dippel, Jack and Zhu, Jasper},
  title =	{{An Improved Approximation Algorithm for the Matching Augmentation Problem}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.38},
  URN =		{urn:nbn:de:0030-drops-154714},
  doi =		{10.4230/LIPIcs.ISAAC.2021.38},
  annote =	{Keywords: 2-Edge connected graph, 2-edge covers, approximation algorithms, connectivity augmentation, forest augmentation problem, matching augmentation problem, network design}
}
  • Refine by Type
  • 4 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2023
  • 1 2021

  • Refine by Author
  • 1 Allen, Bradley P.
  • 1 Cheriyan, Joseph
  • 1 Cummings, Robert
  • 1 Dippel, Jack
  • 1 Groth, Paul
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 1 Computing methodologies → Machine learning
  • 1 Computing methodologies → Natural language processing
  • 1 Computing methodologies → Philosophical/theoretical foundations of artificial intelligence
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 1 2-Edge connected graph
  • 1 2-edge covers
  • 1 approximation algorithms
  • 1 combinatorial optimization
  • 1 connectivity augmentation
  • 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