LIPIcs, Volume 67
ITCS 2017, January 9-11, 2017, Berkeley, CA, USA
Editors: Christos H. Papadimitriou
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Susanne Armbruster, Matthias Mnich, and Martin Nägele. A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{armbruster_et_al:LIPIcs.APPROX/RANDOM.2024.1, author = {Armbruster, Susanne and Mnich, Matthias and N\"{a}gele, Martin}, title = {{A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {1:1--1:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.1}, URN = {urn:nbn:de:0030-drops-209943}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.1}, annote = {Keywords: Travelling Salesperson Problem, precedence constraints, linear programming, approximation algorithms} }
Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)
Kaya Alpturer and S. Matthew Weinberg. Optimal RANDAO Manipulation in Ethereum. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alpturer_et_al:LIPIcs.AFT.2024.10, author = {Alpturer, Kaya and Weinberg, S. Matthew}, title = {{Optimal RANDAO Manipulation in Ethereum}}, booktitle = {6th Conference on Advances in Financial Technologies (AFT 2024)}, pages = {10:1--10:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-345-4}, ISSN = {1868-8969}, year = {2024}, volume = {316}, editor = {B\"{o}hme, Rainer and Kiffer, Lucianna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.10}, URN = {urn:nbn:de:0030-drops-209467}, doi = {10.4230/LIPIcs.AFT.2024.10}, annote = {Keywords: Proof of Stake, Consensus, Blockchain, Ethereum, Randomness manipulation} }
Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)
Zeta Avarikioti, Stefan Schmid, and Samarth Tiwari. Musketeer: Incentive-Compatible Rebalancing for Payment Channel Networks. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{avarikioti_et_al:LIPIcs.AFT.2024.13, author = {Avarikioti, Zeta and Schmid, Stefan and Tiwari, Samarth}, title = {{Musketeer: Incentive-Compatible Rebalancing for Payment Channel Networks}}, booktitle = {6th Conference on Advances in Financial Technologies (AFT 2024)}, pages = {13:1--13:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-345-4}, ISSN = {1868-8969}, year = {2024}, volume = {316}, editor = {B\"{o}hme, Rainer and Kiffer, Lucianna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.13}, URN = {urn:nbn:de:0030-drops-209494}, doi = {10.4230/LIPIcs.AFT.2024.13}, annote = {Keywords: Blockchains, Payment Channel Networks, Rebalancing, Game Theory} }
Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)
Linda Cai, Jingyi Liu, S. Matthew Weinberg, and Chenghan Zhou. Profitable Manipulations of Cryptographic Self-Selection Are Statistically Detectable. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cai_et_al:LIPIcs.AFT.2024.30, author = {Cai, Linda and Liu, Jingyi and Weinberg, S. Matthew and Zhou, Chenghan}, title = {{Profitable Manipulations of Cryptographic Self-Selection Are Statistically Detectable}}, booktitle = {6th Conference on Advances in Financial Technologies (AFT 2024)}, pages = {30:1--30:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-345-4}, ISSN = {1868-8969}, year = {2024}, volume = {316}, editor = {B\"{o}hme, Rainer and Kiffer, Lucianna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.30}, URN = {urn:nbn:de:0030-drops-209660}, doi = {10.4230/LIPIcs.AFT.2024.30}, annote = {Keywords: Blockchain, Cryptocurrency, Proof-of-Stake, Strategic Mining, Statistical Detection} }
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Véronique Bruyère, Christophe Grandmont, and Jean-François Raskin. As Soon as Possible but Rationally. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bruyere_et_al:LIPIcs.CONCUR.2024.14, author = {Bruy\`{e}re, V\'{e}ronique and Grandmont, Christophe and Raskin, Jean-Fran\c{c}ois}, title = {{As Soon as Possible but Rationally}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {14:1--14:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak 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.CONCUR.2024.14}, URN = {urn:nbn:de:0030-drops-207869}, doi = {10.4230/LIPIcs.CONCUR.2024.14}, annote = {Keywords: Games played on graphs, rational verification, rational synthesis, Nash equilibrium, Pareto-optimality, quantitative reachability objectives} }
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Marnix Suilen, Marck van der Vegt, and Sebastian Junges. A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{suilen_et_al:LIPIcs.CONCUR.2024.40, author = {Suilen, Marnix and van der Vegt, Marck and Junges, Sebastian}, title = {{A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {40:1--40:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak 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.CONCUR.2024.40}, URN = {urn:nbn:de:0030-drops-208120}, doi = {10.4230/LIPIcs.CONCUR.2024.40}, annote = {Keywords: Markov Decision Processes, partial observability, linear-time Objectives} }
Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Emir Demirović, Ciaran McCreesh, Matthew J. McIlree, Jakob Nordström, Andy Oertel, and Konstantin Sidorov. Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{demirovic_et_al:LIPIcs.CP.2024.9, author = {Demirovi\'{c}, Emir and McCreesh, Ciaran and McIlree, Matthew J. and Nordstr\"{o}m, Jakob and Oertel, Andy and Sidorov, Konstantin}, title = {{Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {9:1--9:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.9}, URN = {urn:nbn:de:0030-drops-206948}, doi = {10.4230/LIPIcs.CP.2024.9}, annote = {Keywords: Proof logging, dynamic programming, decision diagrams} }
Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Artem Kaznatcheev and Melle van Marle. Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kaznatcheev_et_al:LIPIcs.CP.2024.17, author = {Kaznatcheev, Artem and van Marle, Melle}, title = {{Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {17:1--17:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.17}, URN = {urn:nbn:de:0030-drops-207021}, doi = {10.4230/LIPIcs.CP.2024.17}, annote = {Keywords: valued constraint satisfaction problem, steepest ascent, local search, bounded treewidth, intractability} }
Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Jorke M. de Vlas. On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 35:1-35:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{devlas:LIPIcs.CP.2024.35, author = {de Vlas, Jorke M.}, title = {{On the Complexity of Integer Programming with Fixed-Coefficient Scaling}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {35:1--35:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.35}, URN = {urn:nbn:de:0030-drops-207203}, doi = {10.4230/LIPIcs.CP.2024.35}, annote = {Keywords: constraint satisfaction problems, integer programming, CSP dichotomy} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Archit Chauhan, Samir Datta, Chetan Gupta, and Vimal Raj Sharma. The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chauhan_et_al:LIPIcs.MFCS.2024.43, author = {Chauhan, Archit and Datta, Samir and Gupta, Chetan and Sharma, Vimal Raj}, title = {{The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {43:1--43:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.43}, URN = {urn:nbn:de:0030-drops-205992}, doi = {10.4230/LIPIcs.MFCS.2024.43}, annote = {Keywords: Graph Algorithms, EvenPath, Polynomial-time Algorithms, Reachability} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt. Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goedgebeur_et_al:LIPIcs.MFCS.2024.55, author = {Goedgebeur, Jan and Jooken, Jorik and Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l} and Schaudt, Oliver}, title = {{Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {55:1--55:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.55}, URN = {urn:nbn:de:0030-drops-206110}, doi = {10.4230/LIPIcs.MFCS.2024.55}, annote = {Keywords: graph homomorphism, critical graphs, hereditary graph classes} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Michał Makowski. On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{makowski:LIPIcs.MFCS.2024.73, author = {Makowski, Micha{\l}}, title = {{On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {73:1--73:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.73}, URN = {urn:nbn:de:0030-drops-206291}, doi = {10.4230/LIPIcs.MFCS.2024.73}, annote = {Keywords: Conditional independence implication, exponential time, tiling problem} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Marta Piecyk. C_{2k+1}-Coloring of Bounded-Diameter Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{piecyk:LIPIcs.MFCS.2024.78, author = {Piecyk, Marta}, title = {{C\underline\{2k+1\}-Coloring of Bounded-Diameter Graphs}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {78:1--78:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.78}, URN = {urn:nbn:de:0030-drops-206348}, doi = {10.4230/LIPIcs.MFCS.2024.78}, annote = {Keywords: graph homomorphism, odd cycles, diameter} }
Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)
Markus Iser and Christoph Jabs. Global Benchmark Database. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 18:1-18:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{iser_et_al:LIPIcs.SAT.2024.18, author = {Iser, Markus and Jabs, Christoph}, title = {{Global Benchmark Database}}, booktitle = {27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)}, pages = {18:1--18:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-334-8}, ISSN = {1868-8969}, year = {2024}, volume = {305}, editor = {Chakraborty, Supratik and Jiang, Jie-Hong Roland}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.18}, URN = {urn:nbn:de:0030-drops-205405}, doi = {10.4230/LIPIcs.SAT.2024.18}, annote = {Keywords: Maintenance and Distribution of Benchmark Instances and their Features} }
Feedback for Dagstuhl Publishing