Methods for Solving Extremal Problems in Practice

Author Michael Frank



PDF
Thumbnail PDF

File

OASIcs.ICLP.2016.21.pdf
  • Filesize: 381 kB
  • 6 pages

Document Identifiers

Author Details

Michael Frank

Cite AsGet BibTex

Michael Frank. Methods for Solving Extremal Problems in Practice. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016). Open Access Series in Informatics (OASIcs), Volume 52, pp. 21:1-21:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/OASIcs.ICLP.2016.21

Abstract

During the 20 th century there has been an incredible progress in solving theoretically hard problems in practice. One of the most prominent examples is the DPLL algorithm and its derivatives to solve the Boolean satisfiability problem, which can handle instances with millions of variables and clauses in reasonable time, notwithstanding the theoretical difficulty of solving the problem. Despite this progress, there are classes of problems that contain especially hard instances, which have remained open for decades despite their relative small size. One such class is the class of extremal problems, which typically involve finding a combinatorial object under some constraints (e.g, the search for Ramsey numbers). In recent years, a number of specialized methods have emerged to tackle extremal problems. Most of these methods are applied to a specific problem, despite the fact there is a great deal in common between different problems. Following a meticulous examination of these methods, we would like to extend them to handle general extremal problems. Further more, we would like to offer ways to exploit the general structure of extremal problems in order to develop constraints and symmetry breaking techniques which will, hopefully, improve existing tools. The latter point is of immense importance in the context of extremal problems, which often hamper existing tools when there is a great deal of symmetry in the search space, or when not enough is known of the problem structure. For example, if a graph is a solution to a problem instance, in many cases any isomorphic graph will also be a solution. In such cases, existing methods can usually be applied only if the model excludes symmetries.
Keywords
  • Extremal Problems
  • Constraints
  • SAT Solving
  • Logic Programming
  • Parallelism

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Joan Boyar and René Peralta. Tight bounds for the multiplicative complexity of symmetric functions. TCS, 396(1-3):223-246, 2008. Google Scholar
  2. Joan Boyar, René Peralta, and Denis Pochuev. On the multiplicative complexity of Boolean functions over the basis (∧, +, 1). TCS, 235(1):43-57, 2000. Google Scholar
  3. Daniel Bundala and Jakub Zavodny. Optimal sorting networks. In Adrian Horia Dediu, Carlos Martín-Vide, José Luis Sierra-Rodríguez, and Bianca Truthe, editors, Language and Automata Theory and Applications - 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings, volume 8370 of Lecture Notes in Computer Science, pages 236-247. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-04921-2_19.
  4. Michael Codish, Luís Cruz-Filipe, Michael Frank, and Peter Schneider-Kamp. When six gates are not enough. CoRR, abs/1508.05737, 2015. URL: http://arxiv.org/abs/1508.05737.
  5. Michael Codish, Luís Cruz-Filipe, Michael Frank, and Peter Schneider-Kamp. Sorting nine inputs requires twenty-five comparisons. Journal of Computer and System Sciences, 82(3):551-563, 2016. URL: http://dx.doi.org/10.1016/j.jcss.2005.06.002.
  6. Michael Codish, Michael Frank, Avraham Itzhakov, and Alice Miller. Computing the ramsey number r(4, 3, 3) using abstraction and symmetry breaking. CoRR, abs/1510.08266, 2015. URL: http://arxiv.org/abs/1510.08266.
  7. Michael Codish, Alice Miller, Patrick Prosser, and Peter James Stuckey. Breaking symmetries in graph representation. In Francesca Rossi, editor, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China. IJCAI/AAAI, 2013. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6480.
  8. Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001. Google Scholar
  9. Niklas Eén and Niklas Sörensson. Minisat sat solver. URL: http://minisat.se/Main.html.
  10. Thorsten Ehlers and Mike Müller. Faster sorting networks for 17, 19 and 20 inputs. CoRR, abs/1410.2736, 2014. URL: http://arxiv.org/abs/1410.2736.
  11. Thorsten Ehlers and Mike Müller. New bounds on optimal sorting networks. CoRR, abs/1501.06946, 2015. URL: http://arxiv.org/abs/1501.06946.
  12. M. Frank and M. Codish. Logic programming with graph automorphism: Integrating nauty with prolog (a tool paper). Technical report, Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel, 2016. URL: https://www.cs.bgu.ac.il/~frankm/plnauty/.
  13. Hiroshi Fujita. A new lower bound for the ramsey number r(4, 8). CoRR, abs/1212.1328, 2012. URL: http://arxiv.org/abs/1212.1328.
  14. M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, and M. Schneider. Potassco: The Potsdam answer set solving collection. AI Communications, 24(2):107-124, 2011. Google Scholar
  15. Avraham Itzhakov and Michael Codish. Breaking symmetries in graph search with canonizing sets. CoRR, abs/1511.08205, 2015. URL: http://arxiv.org/abs/1511.08205.
  16. Donald E. Knuth. The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998. Google Scholar
  17. B. McKay. nauty user’s guide (version 1.5). Technical Report TR-CS-90-02, Australian National University, Computer Science Department, 1990. Google Scholar
  18. Brendan D. McKay and Stanislaw P. Radziszowski. R(4, 5) = 25. Journal of Graph Theory, 19(3):309-322, 1995. URL: http://dx.doi.org/10.1002/jgt.3190190304.
  19. Amit Metodi and Michael Codish. Compiling finite domain constraints to sat with bee. Theory and Practice of Logic Programming, 12(4-5):465-483, 2012. Google Scholar
  20. Amit Metodi, Michael Codish, and Peter J. Stuckey. Boolean equi-propagation for concise and efficient SAT encodings of combinatorial problems. J. Artif. Intell. Res. (JAIR), 46:303-341, 2013. URL: http://dx.doi.org/10.1613/jair.3809.
  21. Stanislaw P. Radziszowski. Small Ramsey numbers. Electronic Journal of Combinatorics, 1994. Revision #14: January, 2014. URL: http://www.combinatorics.org/.
  22. Mate Soos. CryptoMiniSAT, v2.5.1, 2010. URL: http://www.msoos.org/cryptominisat2.
  23. Meltem Sönmez Turan and René Peralta. The multiplicative complexity of Boolean functions on four and five variables. In Thomas Eisenbarth and Erdinç Öztürk, editors, LightSec 2014, volume 8898 of LNCS, pages 21-33. Springer, 2015. Google Scholar
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