7 Search Results for "Maher, Stephen J."

Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.37
PACE Solver Description: Minimum Hitting Set Computation via Core-Guided MaxSAT Solving

Authors: André Schidler

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

Abstract
This paper describes our hybrid MaxSAT and mixed integer programming approach for finding minimum hitting sets as submitted to the 2025 PACE challenge. We also discuss hitting set specific challenges, lower bounds, preprocessing and design choices.
Cite as

André Schidler. PACE Solver Description: Minimum Hitting Set Computation via Core-Guided MaxSAT Solving. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 37:1-37:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schidler:LIPIcs.IPEC.2025.37,
  author =	{Schidler, Andr\'{e}},
  title =	{{PACE Solver Description: Minimum Hitting Set Computation via Core-Guided MaxSAT Solving}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{37:1--37: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.37},
  URN =		{urn:nbn:de:0030-drops-251692},
  doi =		{10.4230/LIPIcs.IPEC.2025.37},
  annote =	{Keywords: hitting set, maxsat, core-guided}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.32
The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set

Authors: Mario Grobler and Sebastian Siebertz

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

Abstract
The 10th iteration of the of the Parameterized Algorithms and Computational Experiments challenge (PACE) 2025 was devoted to engineer algorithms solving the Dominating Set problem as well as the Hitting Set problem. In contrast to the last iterations, these problems are (under standard assumptions) not fixed-parameter tractable (fpt) in general. However, restricting the structure of the input (e.g. to planar graphs or degenerate graphs for Dominating Set, or to set systems with sets of bounded size for Hitting Set) renders these problems fpt. Following the spirit of the last iterations of the PACE challenge, there is an exact track and a heuristic track for each problem; each track coming with a benchmark set of 100 public instances and 100 private instances. Overall, the PACE 2025 had 71 participants from 25 teams, 13 countries, and 3 continents. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.
Cite as

Mario Grobler and Sebastian Siebertz. The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.IPEC.2025.32,
  author =	{Grobler, Mario and Siebertz, Sebastian},
  title =	{{The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{32:1--32:17},
  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.32},
  URN =		{urn:nbn:de:0030-drops-251644},
  doi =		{10.4230/LIPIcs.IPEC.2025.32},
  annote =	{Keywords: PACE 2025 Report, Dominating Set, Hitting Set, Algorithm Engineering, FPT, Heuristics}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2025.18
The Influence of GenAI on the Evaluation of Computer Programming Students in Higher Education

Authors: Teresa Terroso and Mário Pinto

Published in: OASIcs, Volume 133, 6th International Computer Programming Education Conference (ICPEC 2025)

Abstract
Artificial Intelligence (AI) has assumed an increasingly prominent role in education, transforming the dynamics of teaching and learning while introducing new pedagogical opportunities and challenges. In computer programming education, generative AI tools have had a particularly profound impact. Historically, computer programming education has emphasized problem-solving skills, syntax accuracy, and code efficiency. However, the emergence of generative AI models capable of supporting automatic code generation, producing high-quality code snippets and entire programs, personalized explanations and tutoring, and real-time debugging, has triggered a paradigm shift. These tools make learning processes and assessment less effective and less clear about students' true knowledge. In this context, the paper explores three key dimensions: the broader impact of AI in education, the new challenges that AI presents in teaching and learning computer programming in higher education, and the implications for student assessment, an essential element of the educational process. To investigate these topics, we conducted an online survey targeting Portuguese higher education instructors teaching programming-related courses. Our primary objective was to understand the changes introduced in evaluation methods and criteria due to the growing use of generative AI tools, particularly those focused on code generation.
Cite as

Teresa Terroso and Mário Pinto. The Influence of GenAI on the Evaluation of Computer Programming Students in Higher Education. In 6th International Computer Programming Education Conference (ICPEC 2025). Open Access Series in Informatics (OASIcs), Volume 133, pp. 18:1-18:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{terroso_et_al:OASIcs.ICPEC.2025.18,
  author =	{Terroso, Teresa and Pinto, M\'{a}rio},
  title =	{{The Influence of GenAI on the Evaluation of Computer Programming Students in Higher Education}},
  booktitle =	{6th International Computer Programming Education Conference (ICPEC 2025)},
  pages =	{18:1--18:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-393-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{133},
  editor =	{Queir\'{o}s, Ricardo and Pinto, M\'{a}rio and Portela, Filipe and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2025.18},
  URN =		{urn:nbn:de:0030-drops-240482},
  doi =		{10.4230/OASIcs.ICPEC.2025.18},
  annote =	{Keywords: Generative Artificial Intelligence, Computer Programming Education, Student Assessment, Teaching and Learning, Higher Education}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2023.16
Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion

Authors: Aigerim Saken and Stephen J. Maher

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
Subproblem separation is a common strategy for the acceleration of the logic-based Benders' decomposition (LBBD). However, it has only been applied to problems with an inherently separable subproblem structure. This paper proposes a new method to separate the subproblem using the connected components algorithm. The subproblem separation is applied to the vehicle routing problem with local congestion (VRPLC). Accordingly, new Benders' cuts are derived for the new subproblem formulation. The computational experiments evaluate the effectiveness of subproblem separation for different methods applying new cuts. It is shown that subproblem separation significantly benefits the LBBD scheme.
Cite as

Aigerim Saken and Stephen J. Maher. Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{saken_et_al:OASIcs.ATMOS.2023.16,
  author =	{Saken, Aigerim and Maher, Stephen J.},
  title =	{{Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{16:1--16:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.16},
  URN =		{urn:nbn:de:0030-drops-187771},
  doi =		{10.4230/OASIcs.ATMOS.2023.16},
  annote =	{Keywords: logic-based Benders' decomposition, vehicle routing, subproblem separation, connected components}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.16
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

Authors: Radek Hušek, Dušan Knop, and Tomáš Masařík

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
In the Steiner Tree problem, we are given an edge-weighted undirected graph G = (V,E) and a set of terminals R ⊆ V. The task is to find a connected subgraph of G containing R and minimizing the sum of weights of its edges. Steiner Tree is well known to be NP-complete and is undoubtedly one of the most studied problems in (applied) computer science. We observe that many approximation algorithms for Steiner Tree follow a similar scheme (meta-algorithm) and perform (exhaustively) a similar routine which we call star contraction. Here, by a star contraction, we mean finding a star-like subgraph in (the metric closure of) the input graph minimizing the ratio of its weight to the number of contained terminals minus one; and contract. It is not hard to see that the well-known MST-approximation seeks the best star to contract among those containing two terminals only. Zelikovsky’s approximation algorithm follows a similar workflow, finding the best star among those containing three terminals. We perform an empirical study of star contractions with the relaxed condition on the number of terminals in each star contraction motivated by a recent result of Dvořák et al. [Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, STACS 2018]. Furthermore, we propose two improvements of Zelikovsky’s 11/6-approximation algorithm and we empirically confirm that the quality of the solution returned by any of these is better than the one returned by the former algorithm. However, such an improvement is exchanged for a slower running time (up to a multiplicative factor of the number of terminals).
Cite as

Radek Hušek, Dušan Knop, and Tomáš Masařík. Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{husek_et_al:LIPIcs.IPEC.2020.16,
  author =	{Hu\v{s}ek, Radek and Knop, Du\v{s}an and Masa\v{r}{\'\i}k, Tom\'{a}\v{s}},
  title =	{{Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.16},
  URN =		{urn:nbn:de:0030-drops-133193},
  doi =		{10.4230/LIPIcs.IPEC.2020.16},
  annote =	{Keywords: Steiner tree, approximation, star contractions, minimum spanning tree}
}
Document
DOI: 10.4230/OASIcs.Gabbrielli.11
Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy

Authors: Moreno Falaschi, Catuscia Palamidessi, and Marco Romanelli

Published in: OASIcs, Volume 86, Recent Developments in the Design and Implementation of Programming Languages (2020)

Abstract
This paper shows how we can combine the power of machine learning with the flexibility of constraints. More specifically, we show how machine learning models can be represented by first-order logic theories, and how to derive these theories. The advantage of this representation is that it can be augmented with additional formulae, representing constraints of some kind on the data domain. For instance, new knowledge, or potential attackers, or fairness desiderata. We consider various kinds of learning algorithms (neural networks, k-nearest-neighbours, decision trees, support vector machines) and for each of them we show how to infer the FOL formulae. Then we focus on one particular application domain, namely the field of security and privacy. The idea is to represent the potentialities and goals of the attacker as a set of constraints, then use a constraint solver (more precisely, a solver modulo theories) to verify the satisfiability. If a solution exists, then it means that an attack is possible, otherwise, the system is safe. We show various examples from different areas of security and privacy; specifically, we consider a side-channel attack on a password checker, a malware attack on smart health systems, and a model-inversion attack on a neural network.
Cite as

Moreno Falaschi, Catuscia Palamidessi, and Marco Romanelli. Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy. In Recent Developments in the Design and Implementation of Programming Languages. Open Access Series in Informatics (OASIcs), Volume 86, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{falaschi_et_al:OASIcs.Gabbrielli.11,
  author =	{Falaschi, Moreno and Palamidessi, Catuscia and Romanelli, Marco},
  title =	{{Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy}},
  booktitle =	{Recent Developments in the Design and Implementation of Programming Languages},
  pages =	{11:1--11:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-171-9},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{86},
  editor =	{de Boer, Frank S. and Mauro, Jacopo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Gabbrielli.11},
  URN =		{urn:nbn:de:0030-drops-132338},
  doi =		{10.4230/OASIcs.Gabbrielli.11},
  annote =	{Keywords: Constraints, machine learning, privacy, security}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.6
Distributed Domain Propagation

Authors: Robert Lion Gottwald, Stephen J. Maher, and Yuji Shinano

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite its simplicity, portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after the domain of a variable has been reduced. In this paper we introduce distributed domain propagation, a technique that shares bound tightenings across solvers to trigger further domain propagations. We investigate its impact in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions, they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.
Cite as

Robert Lion Gottwald, Stephen J. Maher, and Yuji Shinano. Distributed Domain Propagation. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 6:1-6:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gottwald_et_al:LIPIcs.SEA.2017.6,
  author =	{Gottwald, Robert Lion and Maher, Stephen J. and Shinano, Yuji},
  title =	{{Distributed Domain Propagation}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{6:1--6:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.6},
  URN =		{urn:nbn:de:0030-drops-76236},
  doi =		{10.4230/LIPIcs.SEA.2017.6},
  annote =	{Keywords: mixed integer programming, parallelization, domain propagation, portfolio solvers}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2023
  • 2 2020
  • 1 2017

  • Refine by Author
  • 2 Maher, Stephen J.
  • 1 Falaschi, Moreno
  • 1 Gottwald, Robert Lion
  • 1 Grobler, Mario
  • 1 Hušek, Radek
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 3 OASIcs

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Applied computing → Computer-managed instruction
  • 1 Applied computing → Transportation
  • 1 Computing methodologies
  • 1 Computing methodologies → Learning paradigms
  • Show More...

  • Refine by Keyword
  • 1 Algorithm Engineering
  • 1 Computer Programming Education
  • 1 Constraints
  • 1 Dominating Set
  • 1 FPT
  • 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