Last Year

%0 Conference Proceedings %A Abboud, Amir %A Bringmann, Karl %A Khoury, Seri %A Zamir, Or %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Hardness of Approximation in p via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond : %G eng %U http://hdl.handle.net/21.11116/0000-000B-4797-B %R 10.1145/3519935.3520066 %D 2022 %B 54th Annual ACM Symposium on Theory of Computing %Z date of event: 2022-06-20 - 2022-06-24 %C Rome, Italy %B STOC '22 %E Leonardi, Stefano; Gupta, Anupam %P 1487 - 1500 %I ACM %@ 978-1-4503-9264-8

%0 Journal Article %A Abboud, Amir %A Bringmann, Karl %A Hermelin, Danny %A Shabtay, Dvir %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Scheduling Lower Bounds via AND Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-000B-153C-B %R 10.1016/j.jcss.2022.01.005 %7 2022 %D 2022 %J Journal of Computer and System Sciences %V 127 %& 29 %P 29 - 40 %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Abboud, Amir %A Bringmann, Karl %A Hermelin, Danny %A Shabtay, Dvir %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T SETH-Based Lower Bounds for Subset Sum and Bicriteria Path : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1543-2 %R 10.1145/3450524 %7 2022 %D 2022 %J ACM Transactions on Algorithms %V 18 %N 1 %& 1 %P 1 - 22 %Z sequence number: 6 %I ACM %C New York, NY %@ false

%0 Journal Article %A Agrawal, Akanksha %A Lokshtanov, Daniel %A Misra, Pranabendu %A Saurabh, Saket %A Zehavi, Meirav %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Erdős–Pósa Property of Obstructions to Interval Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000B-589A-5 %R 10.1002/jgt.22895 %7 2022 %D 2022 %J Journal of Graph Theory %V 102 %N 4 %& 702 %P 702 - 727 %I John Wiley & Sons. %C New York %@ false

%0 Report %A Akrami, Hannaneh %A Alon, Noga %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %A Mehta, Ruta %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T EFX Allocations: Simplifications and Improvements : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1FEB-A %U https://arxiv.org/abs/2205.07638 %D 2022 %X The existence of EFX allocations is a fundamental open problem in discrete<br>fair division. Given a set of agents and indivisible goods, the goal is to<br>determine the existence of an allocation where no agent envies another<br>following the removal of any single good from the other agent's bundle. Since<br>the general problem has been illusive, progress is made on two fronts: $(i)$<br>proving existence when the number of agents is small, $(ii)$ proving existence<br>of relaxations of EFX. In this paper, we improve results on both fronts (and<br>simplify in one of the cases).<br> We prove the existence of EFX allocations with three agents, restricting only<br>one agent to have an MMS-feasible valuation function (a strict generalization<br>of nice-cancelable valuation functions introduced by Berger et al. which<br>subsumes additive, budget-additive and unit demand valuation functions). The<br>other agents may have any monotone valuation functions. Our proof technique is<br>significantly simpler and shorter than the proof by Chaudhury et al. on<br>existence of EFX allocations when there are three agents with additive<br>valuation functions and therefore more accessible.<br> Secondly, we consider relaxations of EFX allocations, namely, approximate-EFX<br>allocations and EFX allocations with few unallocated goods (charity). Chaudhury<br>et al. showed the existence of $(1-\epsilon)$-EFX allocation with<br>$O((n/\epsilon)^{\frac{4}{5}})$ charity by establishing a connection to a<br>problem in extremal combinatorics. We improve their result and prove the<br>existence of $(1-\epsilon)$-EFX allocations with $\tilde{O}((n/<br>\epsilon)^{\frac{1}{2}})$ charity. In fact, some of our techniques can be used<br>to prove improved upper-bounds on a problem in zero-sum combinatorics<br>introduced by Alon and Krivelevich.<br> %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Conference Proceedings %A Akrami, Hannaneh %A Ray Chaudhury, Bhaskar %A Hoefer, Martin %A Mehlhorn, Kurt %A Schmalhofer, Marco %A Shahkarami, Golnoosh %A Varricchio, Giovanna %A Vermande, Quentin %A van Wijland, Ernest %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Maximizing Nash Social Welfare in 2-Value Instances : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1FC6-3 %R 10.1609/aaai.v36i5.20402 %D 2022 %B 36th AAAI Conference on Artificial Intelligence %Z date of event: 2022-02-22 - 2022-03-01 %C Virtual Conference %B Proceedings of the 36th AAAI Conference on Artificial Intelligence %P 4760 - 4767 %I AAAI %@ 978-1-57735-876-3 %U https://ojs.aaai.org/index.php/AAAI/article/view/20402

%0 Report %A Akrami, Hannaneh %A Ray Chaudhury, Bhaskar %A Hoefer, Martin %A Mehlhorn, Kurt %A Schmalhofer, Marco %A Shahkarami, Golnoosh %A Varricchio, Giovanna %A Vermande, Quentin %A van Wijland, Ernest %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1FD5-2 %U https://arxiv.org/abs/2207.10949 %D 2022 %X We consider the problem of maximizing the Nash social welfare when allocating<br>a set $G$ of indivisible goods to a set $N$ of agents. We study instances, in<br>which all agents have 2-value additive valuations: The value of a good $g \in<br>G$ for an agent $i \in N$ is either $1$ or $s$, where $s$ is an odd multiple of<br>$\frac{1}{2}$ larger than one. We show that the problem is solvable in<br>polynomial time. Akrami et at. showed that this problem is solvable in<br>polynomial time if $s$ is integral and is NP-hard whenever $s = \frac{p}{q}$,<br>$p \in \mathbb{N}$ and $q\in \mathbb{N}$ are co-prime and $p > q \ge 3$. For<br>the latter situation, an approximation algorithm was also given. It obtains an<br>approximation ratio of at most $1.0345$. Moreover, the problem is APX-hard,<br>with a lower bound of $1.000015$ achieved at $\frac{p}{q} = \frac{5}{4}$. The<br>case $q = 2$ and odd $p$ was left open.<br> In the case of integral $s$, the problem is separable in the sense that the<br>optimal allocation of the heavy goods (= value $s$ for some agent) is<br>independent of the number of light goods (= value $1$ for all agents). This<br>leads to an algorithm that first computes an optimal allocation of the heavy<br>goods and then adds the light goods greedily. This separation no longer holds<br>for $s = \frac{3}{2}$; a simple example is given in the introduction. Thus an<br>algorithm has to consider heavy and light goods together. This complicates<br>matters considerably. Our algorithm is based on a collection of improvement<br>rules that transfers any allocation into an optimal allocation and exploits a<br>connection to matchings with parity constraints.<br> %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Conference Proceedings %A Akrami, Hannaneh %A Rezvan, Rojin %A Seddighin, Masoud %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T An EF2X Allocation Protocol for Restricted Additive Valuations : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1FFA-9 %R 10.24963/ijcai.2022/3 %D 2022 %B Thirty-First International Joint Conference on Artificial Intelligence %Z date of event: 2022-07-23 - 2022-07-29 %C Vienna, Austria %B Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence %E de Raedt, Luc %P 17 - 23 %I IJCAI %@ 978-1-956792-00-3

%0 Report %A Akrami, Hannaneh %A Rezvan, Rojin %A Seddighin, Masoud %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T An EF2X Allocation Protocol for Restricted Additive Valuations : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1FF3-0 %U https://arxiv.org/abs/2202.13676 %D 2022 %X We study the problem of fairly allocating a set of $m$ indivisible goods to a<br>set of $n$ agents. Envy-freeness up to any good (EFX) criteria -- which<br>requires that no agent prefers the bundle of another agent after removal of any<br>single good -- is known to be a remarkable analogous of envy-freeness when the<br>resource is a set of indivisible goods. In this paper, we investigate EFX<br>notion for the restricted additive valuations, that is, every good has some<br>non-negative value, and every agent is interested in only some of the goods.<br> We introduce a natural relaxation of EFX called EFkX which requires that no<br>agent envies another agent after removal of any $k$ goods. Our main<br>contribution is an algorithm that finds a complete (i.e., no good is discarded)<br>EF2X allocation for the restricted additive valuations. In our algorithm we<br>devise new concepts, namely "configuration" and "envy-elimination" that might<br>be of independent interest.<br> We also use our new tools to find an EFX allocation for restricted additive<br>valuations that discards at most $\lfloor n/2 \rfloor -1$ goods. This improves<br>the state of the art for the restricted additive valuations by a factor of $2$.<br> %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Journal Article %A Amanatidis, Georgios %A Kleer, Pieter %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-000A-567A-D %R 10.1137/20M1352697 %7 2022 %D 2022 %J SIAM Journal on Discrete Mathematics %V 36 %N 1 %& 118 %P 118 - 146 %I The Society %C Philadelphia, Pa. %@ false

%0 Journal Article %A Amiri, Saeed Akhoondian %A Wiederhake, Ben %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Distributed Distance-r Dominating Set on Sparse High-Girth Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000A-9DFE-8 %R 10.1016/j.tcs.2022.01.001 %7 2022 %D 2022 %J Theoretical Computer Science %V 906 %& 18 %P 18 - 31 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Anagnostides, Ioannis %A Lenzen, Christoph %A Haeupler, Bernhard %A Zuzic, Goran %A Gouleakis, Themis %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts : %G eng %U http://hdl.handle.net/21.11116/0000-000C-7314-C %R 10.4230/LIPIcs.DISC.2022.6 %U urn:nbn:de:0030-drops-171978 %D 2022 %B 36th International Symposium on Distributed Computing %Z date of event: 2022-10-25 - 2022-10-27 %C Augusta, GA, USA %B 36th International Symposium on Distributed Computing %E Scheideler, Christian %P 1 - 20 %Z sequence number: 6 %I Schloss Dagstuhl %@ 978-3-95977-210-5 %B Leibniz International Proceedings in Informatics %N 246 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2022/17197/https://creativecommons.org/licenses/by/4.0/legalcode

%0 Journal Article %A An, Haozhe %A Gurumukhani, Mohit %A Impagliazzo, Russell %A Jaber, Michael %A K&#252;nnemann, Marvin %A Parga Nina, Maria Paula %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Fine-Grained Complexity of Multi-Dimensional Ordering Properties : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1F9C-3 %R 10.1007/s00453-022-01014-x %7 2022 %D 2022 %J Algorithmica %V 84 %& 3156 %P 3156 - 3191 %I Springer-Verlag %C New York %@ false

%0 Conference Proceedings %A Antoniadis, Antonios %A Jabbarzade, Peyman %A Shahkarami, Golnoosh %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Novel Prediction Setup for Online Speed-Scaling : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1FBA-1 %R 10.4230/LIPIcs.SWAT.2022.9 %U urn:nbn:de:0030-drops-161693 %U https://drops.dagstuhl.de/opus/volltexte/2022/16169/ %D 2022 %B 18th Scandinavian Symposium and Workshops on Algorithm Theory %Z date of event: 2022-06-27 - 2022-06-29 %C T&#243;rshavn, Faroe Islands %B 18th Scandinavian Symposium and Workshops on Algorithm Theory %E Czumai, Artur; Xin, Qin %P 1 - 20 %Z sequence number: 9 %I Schloss Dagstuhl %@ 978-3-95977-236-5 %B Leibniz International Proceedings in Informatics %N 227 %@ false

%0 Report %A Antoniadis, Antonios %A Jabbarzade Ganje, Peyman %A Shahkarami, Golnoosh %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Novel Prediction Setup for Online Speed-Scaling : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1FBE-D %U https://arxiv.org/abs/2112.03082 %D 2022 %X Given the rapid rise in energy demand by data centers and computing systems<br>in general, it is fundamental to incorporate energy considerations when<br>designing (scheduling) algorithms. Machine learning can be a useful approach in<br>practice by predicting the future load of the system based on, for example,<br>historical data. However, the effectiveness of such an approach highly depends<br>on the quality of the predictions and can be quite far from optimal when<br>predictions are sub-par. On the other hand, while providing a worst-case<br>guarantee, classical online algorithms can be pessimistic for large classes of<br>inputs arising in practice.<br> This paper, in the spirit of the new area of machine learning augmented<br>algorithms, attempts to obtain the best of both worlds for the classical,<br>deadline based, online speed-scaling problem: Based on the introduction of a<br>novel prediction setup, we develop algorithms that (i) obtain provably low<br>energy-consumption in the presence of adequate predictions, and (ii) are robust<br>against inadequate predictions, and (iii) are smooth, i.e., their performance<br>gradually degrades as the prediction error increases.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Learning, cs.LG

%0 Conference Proceedings %A Apers, Simon %A Efron, Yuval %A Gawrychowski, Pawe&#322; %A Lee, Troy %A Mukhopadhyay, Sagnik %A Nanongkai, Danupon %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Cut Query Algorithms with Star Contraction : %G eng %U http://hdl.handle.net/21.11116/0000-000C-26C5-B %R 10.1109/FOCS54457.2022.00055 %D 2022 %B IEEE 63rd Annual Symposium on Foundations of Computer Science %Z date of event: 2022-10-31 - 2022-11-03 %C Denver, CO, USA %B FOCS 2022 %P 507 - 518 %I IEEE %@ 978-1-6654-5519-0

%0 Conference Proceedings %A Banyassady, Bahareh %A de Berg, Mark %A Bringmann, Karl %A Buchin, Kevin %A Fernau, Henning %A Halperin, Dan %A Kostitsyna, Irina %A Okamoto, Yoshio %A Slot, Stijn %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations %T Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1553-0 %R 10.4230/LIPIcs.SoCG.2022.12 %U urn:nbn:de:0030-drops-160203 %D 2022 %B 38th International Symposium on Computational Geometry %Z date of event: 2022-06-07 - 2022-06-10 %C Berlin, Germany %B 38th International Symposium on Computational Geometry %E Goaoc, Xavier; Kerber, Michael %P 1 - 16 %Z sequence number: 12 %I Schloss Dagstuhl %@ 978-3-95977-227-3 %B Leibniz International Proceedings in Informatics %N 224 %@ false

%0 Journal Article %A Beier, Ren&#233; %A R&#246;glin, Heiko %A R&#246;sner, Clemens %A V&#246;cking, Berthold %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T The Smoothed Number of Pareto-optimal Solutions in Bicriteria Integer Optimization : %G eng %U http://hdl.handle.net/21.11116/0000-000B-58A2-B %R 10.1007/s10107-022-01885-6 %7 2022 %D 2022 %J Mathematical Programming / A %I Springer %C Heidelberg %@ false

%0 Conference Proceedings %A Bernstein, Aaron %A Nanongkai, Danupon %A Wulff-Nilsen, Christian %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Negative-Weight Single-Source Shortest Paths in Near-linear Time : %G eng %U http://hdl.handle.net/21.11116/0000-000C-26C9-7 %R 10.1109/FOCS54457.2022.00063 %D 2022 %B IEEE 63rd Annual Symposium on Foundations of Computer Science %Z date of event: 2022-10-31 - 2022-11-03 %C Denver, CO, USA %B FOCS 2022 %P 600 - 611 %I IEEE %@ 978-1-6654-5519-0

%0 Report %A Bhattacharya, Sayan %A Kiss, Peter %A Saranurak, Thatchaphol %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching : %G eng %U http://hdl.handle.net/21.11116/0000-000C-2696-0 %U https://arxiv.org/abs/2212.00189 %D 2022 %X We study sublinear time algorithms for estimating the size of maximum<br>matching. After a long line of research, the problem was finally settled by<br>Behnezhad [FOCS'22], in the regime where one is willing to pay an approximation<br>factor of $2$. Very recently, Behnezhad et al.[SODA'23] improved the<br>approximation factor to $(2-\frac{1}{2^{O(1/\gamma)}})$ using $n^{1+\gamma}$<br>time. This improvement over the factor $2$ is, however, minuscule and they<br>asked if even $1.99$-approximation is possible in $n^{2-\Omega(1)}$ time. We<br>give a strong affirmative answer to this open problem by showing<br>$(1.5+\epsilon)$-approximation algorithms that run in<br>$n^{2-\Theta(\epsilon^{2})}$ time. Our approach is conceptually simple and<br>diverges from all previous sublinear-time matching algorithms: we show a<br>sublinear time algorithm for computing a variant of the edge-degree constrained<br>subgraph (EDCS), a concept that has previously been exploited in dynamic<br>[Bernstein Stein ICALP'15, SODA'16], distributed [Assadi et al. SODA'19] and<br>streaming [Bernstein ICALP'20] settings, but never before in the sublinear<br>setting. Independent work: Behnezhad, Roghani and Rubinstein [BRR'23]<br>independently showed sublinear algorithms similar to our Theorem 1.2 in both<br>adjacency list and matrix models. Furthermore, in [BRR'23], they show<br>additional results on strictly better-than-1.5 approximate matching algorithms<br>in both upper and lower bound sides.<br> %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Blikstad, Joakim %A Brand, Jan Van Den %A Efron, Yuval %A Mukhopadhyay, Sagnik %A Nanongkai, Danupon %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Nearly Optimal Communication and Query Complexity of Bipartite Matching : %G eng %U http://hdl.handle.net/21.11116/0000-000C-26CF-1 %R 10.1109/FOCS54457.2022.00113 %D 2022 %B IEEE 63rd Annual Symposium on Foundations of Computer Science %Z date of event: 2022-10-31 - 2022-11-03 %C Denver, CO, USA %B FOCS 2022 %P 1174 - 1185 %I IEEE %@ 978-1-6654-5519-0

%0 Journal Article %A Bonifaci, Vincenzo %A Facca, Enrico %A Folz, Frederic %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %A Morigi, Giovanna %A Shahkarami, Golnoosh %A Vermande, Quentin %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Physarum-inspired Multi-commodity Flow Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-000A-28A1-3 %R 10.1016/j.tcs.2022.02.001 %7 2022 %D 2022 %J Theoretical Computer Science %V 920 %& 1 %P 1 - 20 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Boodaghians, Shant %A Ray Chaudhury, Bhaskar %A Mehta, Ruta %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores : %G eng %U http://hdl.handle.net/21.11116/0000-000C-A3BB-9 %R 10.1137/1.9781611977073 %D 2022 %B Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2022-01-09 - 2022-01-12 %C Virtual %B Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms %E Naor, Seffi; Buchbinder, Niv %P 2285 - 2302 %I SIAM %@ 978-1-61197-707-3

%0 Report %A Bria&#324;ski, Marcin %A Joret, Gwena&#235;l %A Majewski, Konrad %A Micek, Piotr %A Seweryn, Micha&#322; T. %A Sharma, Roohani %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Treedepth Vs Circumference : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1E81-1 %U https://arxiv.org/abs/2211.11410 %D 2022 %X The circumference of a graph $G$ is the length of a longest cycle in $G$, or<br>$+\infty$ if $G$ has no cycle. Birmel\'e (2003) showed that the treewidth of a<br>graph $G$ is at most its circumference minus one. We strengthen this result for<br>$2$-connected graphs as follows: If $G$ is $2$-connected, then its treedepth is<br>at most its circumference. The bound is best possible and improves on an<br>earlier quadratic upper bound due to Marshall and Wood (2015).<br> %K Mathematics, Combinatorics, math.CO,Computer Science, Discrete Mathematics, cs.DM

%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime : %G eng %U http://hdl.handle.net/21.11116/0000-000B-588D-4 %R 10.1145/3519935.3519990 %D 2022 %B 54th Annual ACM Symposium on Theory of Computing %Z date of event: 2022-06-20 - 2022-06-24 %C Rome, Italy %B STOC '22 %E Leonardi, Stefano; Gupta, Anupam %P 1102 - 1115 %I ACM %@ 978-1-4503-9264-8

%0 Conference Proceedings %A Bringmann, Karl %A Driemel, Anne %A Nusser, Andr&#233; %A Psarros, Ioannis %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fr&#233;chet Distance : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1D7D-9 %R 10.1137/1.9781611977073.25 %D 2022 %B Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2022-01-09 - 2022-01-12 %C Virtual %B Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms %E Naor, Seffi; Buchbinder, Niv %P 517 - 550 %I SIAM %@ 978-1-61197-707-3

%0 Conference Proceedings %A Bringmann, Karl %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1D81-2 %R 10.1137/1.9781611977073.119 %D 2022 %B Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2022-01-09 - 2022-01-12 %C Virtual %B Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms %E Naor, Seffi; Buchbinder, Niv %P 3069 - 3090 %I SIAM %@ 978-1-61197-707-3

%0 Journal Article %A Bringmann, Karl %A Keusch, Ralph %A Lengler, Johannes %A Maus, Yannic %A Molla, Anisur Rahaman %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Greedy Routing and the Algorithmic Small-World Phenomenon : %G eng %U http://hdl.handle.net/21.11116/0000-000A-9DD0-A %R 10.1016/j.jcss.2021.11.003 %7 2022 %D 2022 %J Journal of Computer and System Sciences %V 125 %& 59 %P 59 - 105 %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Bringmann, Karl %A Fischer, Nick %A Hermelin, Danny %A Shabtay, Dvir %A Wellnitz, Philip %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Minimization of Tardy Processing Time on a Single Machine : %G eng %U http://hdl.handle.net/21.11116/0000-0009-FAD4-E %R 10.1007/s00453-022-00928-w %7 2022 %D 2022 %J Algorithmica %V 84 %& 1341 %P 1341 - 1356 %I Springer %C New York %@ false %U https://rdcu.be/cG2A9

%0 Conference Proceedings %A Bringmann, Karl %A Kisfaludi-Bak, S&#225;ndor %A K&#252;nnemann, Marvin %A Marx, D&#225;niel %A Nusser, Andr&#233; %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1560-1 %R 10.4230/LIPIcs.SoCG.2022.20 %U urn:nbn:de:0030-drops-160287 %D 2022 %B 38th International Symposium on Computational Geometry %Z date of event: 2022-06-07 - 2022-06-10 %C Berlin, Germany %B 38th International Symposium on Computational Geometry %E Goaoc, Xavier; Kerber, Michael %P 1 - 17 %Z sequence number: 20 %I Schloss Dagstuhl %@ 978-3-95977-227-3 %B Leibniz International Proceedings in Informatics %N 224 %@ false

%0 Conference Proceedings %A Bringmann, Karl %A Kisfaludi-Bak, S&#225;ndor %A K&#252;nnemann, Marvin %A Nusser, Andr&#233; %A Parsaeian, Zahra %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1572-D %R 10.4230/LIPIcs.SoCG.2022.21 %U urn:nbn:de:0030-drops-160294 %D 2022 %B 38th International Symposium on Computational Geometry %Z date of event: 2022-06-07 - 2022-06-10 %C Berlin, Germany %B 38th International Symposium on Computational Geometry %E Goaoc, Xavier; Kerber, Michael %P 1 - 16 %Z sequence number: 21 %I Schloss Dagstuhl %@ 978-3-95977-227-3 %B Leibniz International Proceedings in Informatics %N 224 %@ false

%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A K&#252;nnemann, Marvin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Structural Investigation of the Approximability of Polynomial-Time Problems : %G eng %U http://hdl.handle.net/21.11116/0000-000B-15B5-1 %R 10.4230/LIPIcs.ICALP.2022.30 %U urn:nbn:de:0030-drops-163713 %D 2022 %B 49th International Colloquium on Automata, Languages, and Programming %Z date of event: 2022-07-04 - 2022-07-08 %C Paris, France %B 49th EATCS International Conference on Automata, Languages, and Programming %E Boja&#324;czyk, Miko&#322;aj; Merelli, Emanuela; Woodruff, David P. %P 1 - 20 %Z sequence number: 30 %I Schloss Dagstuhl %@ 978-3-95977-235-8} %B Leibniz International Proceedings in Informatics %N 229

%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Improved Sublinear-Time Edit Distance for Preprocessed Strings : %G eng %U http://hdl.handle.net/21.11116/0000-000B-163A-C %R 10.4230/LIPIcs.ICALP.2022.32 %U urn:nbn:de:0030-drops-163734 %D 2022 %B 49th International Colloquium on Automata, Languages, and Programming %Z date of event: 2022-07-04 - 2022-07-08 %C Paris, France %B 49th EATCS International Conference on Automata, Languages, and Programming %E Boja&#324;czyk, Miko&#322;aj; Merelli, Emanuela; Woodruff, David P. %P 1 - 20 %Z sequence number: 32 %I Schloss Dagstuhl %@ 978-3-95977-235-8} %B Leibniz International Proceedings in Informatics %N 229

%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1622-6 %R 10.4230/LIPIcs.ICALP.2022.31 %U urn:nbn:de:0030-drops-163727 %D 2022 %B 49th International Colloquium on Automata, Languages, and Programming %Z date of event: 2022-07-04 - 2022-07-08 %C Paris, France %B 49th EATCS International Conference on Automata, Languages, and Programming %E Boja&#324;czyk, Miko&#322;aj; Merelli, Emanuela; Woodruff, David P. %P 1 - 21 %Z sequence number: 31 %I Schloss Dagstuhl %@ 978-3-95977-235-8} %B Leibniz International Proceedings in Informatics %N 229

%0 Conference Proceedings %A Bringmann, Karl %A Carmeli, Nofar %A Mengel, Stefan %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Tight Fine-Grained Bounds for Direct Access on Join Queries : %G eng %U http://hdl.handle.net/21.11116/0000-000B-2037-3 %R 10.1145/3517804.3526234 %D 2022 %B 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems %Z date of event: 2022-06-12 - 2022-06-17 %C Philadelphia, PA, USA %B PODS '22 %E Libkin, Leonid; Barcel&#243;, Pablo; Grez, Alejandro %P 427 - 436 %I ACM %@ 978-1-4503-9260-0

%0 Conference Proceedings %A Buchin, Kevin %A Nusser, Andr&#233; %A Wong, Sampson %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time : %G eng %U http://hdl.handle.net/21.11116/0000-000C-268B-D %R 10.4230/LIPIcs.SoCG.2022.22 %U urn:nbn:de:0030-drops-160307 %D 2022 %B 38th International Symposium on Computational Geometry %Z date of event: 2022-06-07 - 2022-06-10 %C Berlin, Germany %B 38th International Symposium on Computational Geometry %E Goaoc, Xavier; Kerber, Michael %P 1 - 16 %Z sequence number: 22 %I Schloss Dagstuhl %@ 978-3-95977-227-3 %B Leibniz International Proceedings in Informatics %N 224 %@ false

%0 Report %A Caoduro, Marco %A Cslovjecsek, Jana %A Pilipczuk, Micha&#322; %A W&#281;grzycki, Karol %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Independence Number of Intersection Graphs of Axis-Parallel Segments : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1F1D-3 %U https://arxiv.org/abs/2205.15189 %D 2022 %X We prove that for any triangle-free intersection graph of $n$ axis-parallel<br>segments in the plane, the independence number $\alpha$ of this graph is at<br>least $\alpha \ge n/4 + \Omega(\sqrt{n})$. We complement this with a<br>construction of a graph in this class satisfying $\alpha \le n/4 + c \sqrt{n}$<br>for an absolute constant $c$, which demonstrates the optimality of our result.<br> %K Mathematics, Combinatorics, math.CO,Computer Science, Computational Geometry, cs.CG,Computer Science, Discrete Mathematics, cs.DM,

%0 Report %A Charalampopoulos, Panagiotis %A Kociumaka, Tomasz %A Wellnitz, Philip %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Pattern Matching under Edit Distance : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1EC9-1 %U https://arxiv.org/abs/2204.03087 %D 2022 %X We consider the approximate pattern matching problem under the edit distance.<br>Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold<br>$k$, the task is to find the starting positions of all substrings of $T$ that<br>can be transformed to $P$ with at most $k$ edits. More than 20 years ago, Cole<br>and Hariharan [SODA'98, J. Comput.'02] gave an $\mathcal{O}(n+k^4 \cdot n/<br>m)$-time algorithm for this classic problem, and this runtime has not been<br>improved since.<br> Here, we present an algorithm that runs in time $\mathcal{O}(n+k^{3.5}<br>\sqrt{\log m \log k} \cdot n/m)$, thus breaking through this long-standing<br>barrier. In the case where $n^{1/4+\varepsilon} \leq k \leq<br>n^{2/5-\varepsilon}$ for some arbitrarily small positive constant<br>$\varepsilon$, our algorithm improves over the state-of-the-art by polynomial<br>factors: it is polynomially faster than both the algorithm of Cole and<br>Hariharan and the classic $\mathcal{O}(kn)$-time algorithm of Landau and<br>Vishkin [STOC'86, J. Algorithms'89].<br> We observe that the bottleneck case of the alternative $\mathcal{O}(n+k^4<br>\cdot n/m)$-time algorithm of Charalampopoulos, Kociumaka, and Wellnitz<br>[FOCS'20] is when the text and the pattern are (almost) periodic. Our new<br>algorithm reduces this case to a new dynamic problem (Dynamic Puzzle Matching),<br>which we solve by building on tools developed by Tiskin [SODA'10,<br>Algorithmica'15] for the so-called seaweed monoid of permutation matrices. Our<br>algorithm relies only on a small set of primitive operations on strings and<br>thus also applies to the fully-compressed setting (where text and pattern are<br>given as straight-line programs) and to the dynamic setting (where we maintain<br>a collection of strings under creation, splitting, and concatenation),<br>improving over the state of the art.<br> %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Charalampopoulos, Panagiotis %A Kociumaka, Tomasz %A Wellnitz, Philip %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Pattern Matching under Edit Distance: A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1571-D %R 10.1109/FOCS54457.2022.00072 %D 2022 %B IEEE 63rd Annual Symposium on Foundations of Computer Science %Z date of event: 2022-10-31 - 2022-11-03 %C Denver, CO, USA %B FOCS 2022 %P 698 - 707 %I IEEE %@ 978-1-6654-5519-0

%0 Conference Proceedings %A Charalampopoulos, Panagiotis %A Kociumaka, Tomasz %A Pissis, Solon P. %A Radoszewski, Jakub %A Rytter, Wojciech %A Wale&#324;, Tomasz %A Zuba, Wiktor %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations External Organizations %T Approximate Circular Pattern Matching : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1531-5 %R 10.4230/LIPIcs.ESA.2022.35 %U urn:nbn:de:0030-drops-169738 %U https://drops.dagstuhl.de/opus/volltexte/2022/16973/ %D 2022 %B 30th Annual European Symposium on Algorithms %Z date of event: 2022-09-05 - 2022-09-09 %C Berlin/Potsdam, Germany %B 30th Annual European Symposium on Algorithms %E Chechik, Shiri; Navarro, Gonzalo; Rotenberg, Eva; Herman, Grzegorz %P 1 - 19 %Z sequence number: 35 %I Schloss Dagstuhl %@ 978-3-95977-247-1 %B Leibniz International Proceedings in Informatics %N 244 %@ false

%0 Conference Proceedings %A Coudert, David %A Nusser, Andr&#233; %A Viennot, Laurent %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Computing Graph Hyperbolicity Using Dominating Sets : %G eng %U http://hdl.handle.net/21.11116/0000-000C-268E-A %R 10.1137/1.9781611977042.7 %D 2022 %B Symposium on Algorithm Engineering and Experiments %Z date of event: 2022-01-09 - 2022-01-10 %C Alexandria, VA, USA %B Proceedings of the Symposium on Algorithm Engineering and Experiments %E Phillips, Cynthia A.; Speckman, Bettina %P 78 - 90 %I SIAM %@ 978-1-61197-704-2

%0 Journal Article %A Coudert, David %A Nusser, Andr&#233; %A Viennot, Laurent %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Enumeration of Far-Apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation : %G eng %U http://hdl.handle.net/21.11116/0000-000B-FE19-C %R 10.1145/3569169 %7 2022 %D 2022 %J ACM Journal of Experimental Algorithmics %V 27 %Z sequence number: 1.15 %I ACM %C New York, NY %@ false

%0 Report %A Coupette, Corinna %A Vreeken, Jilles %A Rieck, Bastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T All the World's a (Hyper)Graph: A Data Drama : %G eng %U http://hdl.handle.net/21.11116/0000-000C-10C1-7 %U https://arxiv.org/abs/2206.08225 %D 2022 %X We introduce Hyperbard, a dataset of diverse relational data representations<br>derived from Shakespeare's plays. Our representations range from simple graphs<br>capturing character co-occurrence in single scenes to hypergraphs encoding<br>complex communication settings and character contributions as hyperedges with<br>edge-specific node weights. By making multiple intuitive representations<br>readily available for experimentation, we facilitate rigorous representation<br>robustness checks in graph learning, graph mining, and network analysis,<br>highlighting the advantages and drawbacks of specific representations.<br>Leveraging the data released in Hyperbard, we demonstrate that many solutions<br>to popular graph mining problems are highly dependent on the representation<br>choice, thus calling current graph curation practices into question. As an<br>homage to our data source, and asserting that science can also be art, we<br>present all our points in the form of a play.<br> %K Computer Science, Learning, cs.LG,Computer Science, Computation and Language, cs.CL,Computer Science, Computers and Society, cs.CY,cs.SI

%0 Report %A Coupette, Corinna %A Hartung, Dirk %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Sharing and Caring: Creating a Culture of Constructive Criticism in Computational Legal Studies : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1083-D %U https://arxiv.org/abs/2205.01071 %D 2022 %X We introduce seven foundational principles for creating a culture of<br>constructive criticism in computational legal studies. Beginning by challenging<br>the current perception of papers as the primary scholarly output, we call for a<br>more comprehensive interpretation of publications. We then suggest to make<br>these publications computationally reproducible, releasing all of the data and<br>all of the code all of the time, on time, and in the most functioning form<br>possible. Subsequently, we invite constructive criticism in all phases of the<br>publication life cycle. We posit that our proposals will help form our field,<br>and float the idea of marking this maturity by the creation of a modern<br>flagship publication outlet for computational legal studies.<br> %K Computer Science, Computers and Society, cs.CY,Computer Science, Computation and Language, cs.CL

%0 Journal Article %A Coupette, Corinna %A Hartung, Dirk %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Rechtsstrukturvergleichung : %G eng %U http://hdl.handle.net/21.11116/0000-000C-108A-6 %R 10.1628/rabelsz-2022-0082 %7 2022 %D 2022 %J Rabels Zeitschrift f&#252;r ausl&#228;ndisches und internationales Privatrecht %O RabelsZ %V 86 %N 4 %& 935 %P 935 - 975

%0 Conference Proceedings %A Coupette, Corinna %A Dalleiger, Sebastian %A Vreeken, Jilles %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Differentially Describing Groups of Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000C-105C-B %R 10.1609/aaai.v36i4.20312 %D 2022 %B 36th AAAI Conference on Artificial Intelligence %Z date of event: 2022-02-22 - 2022-03-01 %C Virtual Conference %B Proceedings of the 36th AAAI Conference on Artificial Intelligence %P 3959 - 3967 %I AAAI %@ 978-1-57735-876-3 %U https://ojs.aaai.org/index.php/AAAI/article/view/20312/20071

%0 Journal Article %A Coupette, Corinna %A Hartung, Dirk %A Beckedorf, Janis %A Bother, Maximilian %A Katz, Daniel Martin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Law Smells - Defining and Detecting Problematic Patterns in Legal Drafting : %G eng %U http://hdl.handle.net/21.11116/0000-000A-CD04-B %R 10.1007/s10506-022-09315-w %7 2022 %D 2022 %J Artificial Intelligence and Law %I Springer %C New York, NY %@ false

%0 Report %A Coupette, Corinna %A Dalleiger, Sebastian %A Vreeken, Jilles %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Differentially Describing Groups of Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000C-165D-4 %U https://arxiv.org/abs/2201.04064 %D 2022 %X How does neural connectivity in autistic children differ from neural<br>connectivity in healthy children or autistic youths? What patterns in global<br>trade networks are shared across classes of goods, and how do these patterns<br>change over time? Answering questions like these requires us to differentially<br>describe groups of graphs: Given a set of graphs and a partition of these<br>graphs into groups, discover what graphs in one group have in common, how they<br>systematically differ from graphs in other groups, and how multiple groups of<br>graphs are related. We refer to this task as graph group analysis, which seeks<br>to describe similarities and differences between graph groups by means of<br>statistically significant subgraphs. To perform graph group analysis, we<br>introduce Gragra, which uses maximum entropy modeling to identify a<br>non-redundant set of subgraphs with statistically significant associations to<br>one or more graph groups. Through an extensive set of experiments on a wide<br>range of synthetic and real-world graph groups, we confirm that Gragra works<br>well in practice.<br> %K cs.SI,Computer Science, Information Theory, cs.IT,Computer Science, Learning, cs.LG,Mathematics, Information Theory, math.IT

%0 Journal Article %A Croitoru, Cosmina %A Croitoru, Madalina %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Indepth Combinatorial Analysis of Admissible Sets for Abstract Argumentation : %G eng %U http://hdl.handle.net/21.11116/0000-000A-5D72-E %R 10.1007/s10472-022-09785-3 %7 2022 %D 2022 %J Annals of Mathematics and Artificial Intelligence %V 90 %& 1139 %P 1139 - 1158 %I Springer %C New York, NY %@ false

%0 Journal Article %A Cseh, &#193;gnes %A Faenza, Yuri %A Kavitha, Telikepalli %A Powers, Vladlena %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Understanding Popular Matchings via Stable Matchings : %G eng %U http://hdl.handle.net/21.11116/0000-000A-57C3-8 %R 10.1137/19M124770X %7 2022 %D 2022 %J SIAM Journal on Discrete Mathematics %V 36 %N 1 %& 188 %P 188 - 213 %I The Society %C Philadelphia, Pa. %@ false

%0 Report %A Cslovjecsek, Jana %A Pilipczuk, Micha&#322; %A W&#281;grzycki, Karol %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1F75-F %U https://arxiv.org/abs/2212.01620 %D 2022 %X In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are<br>given a weighted set of $n$ axis-parallel rectangles in the plane. The task is<br>to find a subset of pairwise non-overlapping rectangles with the maximum<br>possible total weight. This problem is NP-hard and the best-known<br>polynomial-time approximation algorithm, due to by Chalermsook and Walczak<br>(SODA 2021), achieves approximation factor $O(\log\log n )$. While in the<br>unweighted setting, constant factor approximation algorithms are known, due to<br>Mitchell (FOCS 2021) and to G\'alvez et al. (SODA 2022), it remains open to<br>extend these techniques to the weighted setting.<br> In this paper, we consider MWISR through the lens of parameterized<br>approximation. Grandoni et al. (ESA 2019) gave a $(1-\epsilon)$-approximation<br>algorithm with running time $k^{O(k/\epsilon^8)} n^{O(1/\epsilon^8)}$ time,<br>where $k$ is the number of rectangles in an optimum solution. Unfortunately,<br>their algorithm works only in the unweighted setting and they left it as an<br>open problem to give a parameterized approximation scheme in the weighted<br>setting.<br> Our contribution is a partial answer to the open question of Grandoni et al.<br>(ESA 2019). We give a parameterized approximation algorithm for MWISR that<br>given a parameter $k$, finds a set of non-overlapping rectangles of weight at<br>least $(1-\epsilon) \text{opt}_k$ in $2^{O(k \log(k/\epsilon))}<br>n^{O(1/\epsilon)}$ time, where $\text{opt}_k$ is the maximum weight of a<br>solution of cardinality at most $k$. Note that thus, our algorithm may return a<br>solution consisting of more than $k$ rectangles. To complement this apparent<br>weakness, we also propose a parameterized approximation scheme with running<br>time $2^{O(k^2 \log(k/\epsilon))} n^{O(1)}$ that finds a solution with<br>cardinality at most $k$ and total weight at least $(1-\epsilon)\text{opt}_k$<br>for the special case of axis-parallel segments.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Geometry, cs.CG

%0 Conference Proceedings %A Das, Debarati %A Kociumaka, Tomasz %A Saha, Barna %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1541-3 %R 10.4230/LIPIcs.ICALP.2022.49 %U urn:nbn:de:0030-drops-163902 %U https://drops.dagstuhl.de/opus/volltexte/2022/16390/ %D 2022 %B 49th International Colloquium on Automata, Languages, and Programming %Z date of event: 2022-07-04 - 2022-07-08 %C Paris, France %B 49th EATCS International Conference on Automata, Languages, and Programming %E Boja&#324;czyk, Miko&#322;aj; Merelli, Emanuela; Woodruff, David P. %P 1 - 20 %Z sequence number: 49 %I Schloss Dagstuhl %@ 978-3-95977-235-8 %B Leibniz International Proceedings in Informatics %N 229

%0 Conference Proceedings %A Das, Debarati %A Gilbert, Jacob %A Hajiaghayi, MohammadTaghi %A Kociumaka, Tomasz %A Saha, Barna %A Saleh, Hamed %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T &#213;(n + poly(k))-time Algorithm for Bounded Tree Edit Distance : %G eng %U http://hdl.handle.net/21.11116/0000-000C-153D-9 %R 10.1109/FOCS54457.2022.00071 %D 2022 %B IEEE 63rd Annual Symposium on Foundations of Computer Science %Z date of event: 2022-10-31 - 2022-11-03 %C Denver, CO, USA %B FOCS 2022 %P 686 - 697 %I IEEE %@ 978-1-6654-5519-0

%0 Conference Proceedings %A Esmer, Bari&#351; Can %A Kulik, Ariel %A Marx, D&#225;niel %A Neuen, Daniel %A Sharma, Roohani %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1DA2-D %R 10.4230/LIPIcs.ESA.2022.50 %U urn:nbn:de:0030-drops-169887 %U https://drops.dagstuhl.de/opus/volltexte/2022/16988/ %D 2022 %B 30th Annual European Symposium on Algorithms %Z date of event: 2022-09-05 - 2022-09-09 %C Berlin/Potsdam, Germany %B 30th Annual European Symposium on Algorithms %E Chechik, Shiri; Navarro, Gonzalo; Rotenberg, Eva; Herman, Grzegorz %P 1 - 19 %Z sequence number: 50 %I Schloss Dagstuhl %@ 978-3-95977-247-1 %B Leibniz International Proceedings in Informatics %N 244 %@ false

%0 Conference Proceedings %A Esmer, Bari&#351; Can %A Kulik, Ariel %A Marx, D&#225;niel %A Schepper, Philipp %A W&#281;grzycki, Karol %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Computing Generalized Convolutions Faster Than Brute Force : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1EE6-0 %R 10.4230/LIPIcs.IPEC.2022.12 %U urn:nbn:de:0030-drops-173685 %U https://drops.dagstuhl.de/opus/volltexte/2022/17368/ %D 2022 %B 17th International Symposium on Parameterized and Exact Computation %Z date of event: 2022-09-07 - 2022-09-09 %C Potsdam, Germany %B 17th International Symposium on Parameterized and Exact Computation %E Dell, Holger; Nederlof, Jesper %P 1 - 22 %Z sequence number: 12 %I Schloss Dagstuhl %@ 978-3-95977-260-0 %B Leibniz International Proceedings in Informatics %N 249

%0 Report %A Esmer, Bar&#305;&#351; Can %A Kulik, Ariel %A Marx, D&#225;niel %A Neuen, Daniel %A Sharma, Roohani %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1E6F-8 %U https://arxiv.org/abs/2206.13481 %D 2022 %X We generalize the monotone local search approach of Fomin, Gaspers,<br>Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between<br>parameterized approximation and exponential-time approximation algorithms for<br>monotone subset minimization problems. In a monotone subset minimization<br>problem the input implicitly describes a non-empty set family over a universe<br>of size $n$ which is closed under taking supersets. The task is to find a<br>minimum cardinality set in this family. Broadly speaking, we use approximate<br>monotone local search to show that a parameterized $\alpha$-approximation<br>algorithm that runs in $c^k \cdot n^{O(1)}$ time, where $k$ is the solution<br>size, can be used to derive an $\alpha$-approximation randomized algorithm that<br>runs in $d^n \cdot n^{O(1)}$ time, where $d$ is the unique value in $d \in<br>(1,1+\frac{c-1}{\alpha})$ such that<br>$\mathcal{D}(\frac{1}{\alpha}\|\frac{d-1}{c-1})=\frac{\ln c}{\alpha}$ and<br>$\mathcal{D}(a \|b)$ is the Kullback-Leibler divergence. This running time<br>matches that of Fomin et al. for $\alpha=1$, and is strictly better when<br>$\alpha >1$, for any $c > 1$. Furthermore, we also show that this result can be<br>derandomized at the expense of a sub-exponential multiplicative factor in the<br>running time.<br> We demonstrate the potential of approximate monotone local search by deriving<br>new and faster exponential approximation algorithms for Vertex Cover,<br>$3$-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex<br>Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we<br>get a $1.1$-approximation algorithm for Vertex Cover with running time $1.114^n<br>\cdot n^{O(1)}$, improving upon the previously best known $1.1$-approximation<br>running in time $1.127^n \cdot n^{O(1)}$ by Bourgeois et al. [DAM 2011].<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC

%0 Conference Proceedings %A Firman, Oksana %A Spoerhase, Joachim %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Hypergraph Representation via Axis-Aligned Point-Subspace Cover : %G eng %U http://hdl.handle.net/21.11116/0000-000C-26B3-F %R 10.1007/978-3-030-96731-4_27 %D 2022 %B 16th International Conference and Workshops on Algorithms and Computation %Z date of event: 2022-03-24 - 2022-03-26 %C Jember, Indonesia %B WALCOM: Algorithms and Computation %E Mutzel, Petra; Rahman, Md. Saidur; Slamin %P 328 - 339 %I Springer %@ 978-3-030-96730-7 %B Lecture Notes in Computer Science %N 13174 %U https://rdcu.be/c21qy

%0 Journal Article %A Fomin, Fedor V. %A Golovach, Petr A. %A Lochet, William %A Misra, Pranabendu %A Saurabh, Saket %A Sharma, Roohani %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Parameterized Complexity of Directed Spanner Problems : %G eng %U http://hdl.handle.net/21.11116/0000-0009-BAB8-6 %R 10.1007/s00453-021-00911-x %7 2021 %D 2022 %J Algorithmica %V 84 %& 2292 %P 2292 - 2308 %I Springer-Verlag %C New York %@ false

%0 Journal Article %A F&#252;gger, Matthias %A Kinali, Attila %A Lenzen, Christoph %A Wiederhake, Ben %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance : %G eng %U http://hdl.handle.net/21.11116/0000-0009-201C-4 %R 10.1109/TCAD.2021.3097599 %7 2021 %D 2022 %J IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems %V 41 %N 8 %& 2518 %P 2518 - 2531 %I IEEE %C Piscataway, NJ %@ false

%0 Conference Proceedings %A Galby, Esther %A Marx, D&#225;niel %A Schepper, Philipp %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Parameterized Complexity of Weighted Multicut in Trees : %G eng %U http://hdl.handle.net/21.11116/0000-000B-5925-8 %R 10.1007/978-3-031-15914-5_19 %D 2022 %B 48th International Workshop on Graph-Theoretic Concepts in Computer Science %Z date of event: 2022-06-22 - 2022-06-24 %C T&#252;bingen, Germany %B Graph-Theoretic Concepts in Computer Science %E Bekos, Michael A.; Kaufmann, Michael %P 257 - 270 %I Springer %@ 978-3-031-15913-8 %B Lecture Notes in Computer Science %N 13453

%0 Conference Proceedings %A Galby, Esther %A Marx, D&#225;niel %A Schepper, Philipp %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Domination and Cut Problems on Chordal Graphs with Bounded Leafage : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1DB2-B %R 10.4230/LIPIcs.IPEC.2022.14 %U urn:nbn:de:0030-drops-173704 %U https://drops.dagstuhl.de/opus/volltexte/2022/17370/ %D 2022 %B 17th International Symposium on Parameterized and Exact Computation %Z date of event: 2022-09-07 - 2022-09-09 %C Potsdam, Germany %B 17th International Symposium on Parameterized and Exact Computation %E Dell, Holger; Nederlof, Jesper %P 1 - 24 %Z sequence number: 14 %I Schloss Dagstuhl %@ 978-3-95977-260-0 %B Leibniz International Proceedings in Informatics %N 249

%0 Conference Proceedings %A Galby, Esther %A Khazaliya, Liana %A Mc Inerney, Fionn %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1DB9-4 %R 10.4230/LIPIcs.MFCS.2022.51 %U urn:nbn:de:0030-drops-168496 %U https://drops.dagstuhl.de/opus/volltexte/2022/16849/ %D 2022 %B 47th International Symposium on Mathematical Foundations of Computer Science %Z date of event: 2022-08-22 - 2022-08-26 %C Vienna, Austria %B 47th International Symposium on Mathematical Foundations of Computer Science %E Szeider, Stefan; Ganian, Robert; Silva, Alexandra %P 1 - 15 %Z sequence number: 51 %I Schloss Dagstuhl %@ 978-3-95977-256-3 %B Leibniz International Proceedings in Informatics %N 241

%0 Report %A Galby, Esther %A Marx, D&#225;niel %A Schepper, Philipp %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Parameterized Complexity of Weighted Multicut in Trees : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1DC8-3 %U https://arxiv.org/abs/2205.10105 %D 2022 %X The Edge Multicut problem is a classical cut problem where given an<br>undirected graph $G$, a set of pairs of vertices $\mathcal{P}$, and a budget<br>$k$, the goal is to determine if there is a set $S$ of at most $k$ edges such<br>that for each $(s,t) \in \mathcal{P}$, $G-S$ has no path from $s$ to $t$. Edge<br>Multicut has been relatively recently shown to be fixed-parameter tractable<br>(FPT), parameterized by $k$, by Marx and Razgon [SICOMP 2014], and<br>independently by Bousquet et al. [SICOMP 2018]. In the weighted version of the<br>problem, called Weighted Edge Multicut one is additionally given a weight<br>function $\mathtt{wt} : E(G) \to \mathbb{N}$ and a weight bound $w$, and the<br>goal is to determine if there is a solution of size at most $k$ and weight at<br>most $w$. Both the FPT algorithms for Edge Multicut by Marx et al. and Bousquet<br>et al. fail to generalize to the weighted setting. In fact, the weighted<br>problem is non-trivial even on trees and determining whether Weighted Edge<br>Multicut on trees is FPT was explicitly posed as an open problem by Bousquet et<br>al. [STACS 2009]. In this article, we answer this question positively by<br>designing an algorithm which uses a very recent result by Kim et al. [STOC<br>2022] about directed flow augmentation as subroutine.<br> We also study a variant of this problem where there is no bound on the size<br>of the solution, but the parameter is a structural property of the input, for<br>example, the number of leaves of the tree. We strengthen our results by stating<br>them for the more general vertex deletion version.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC

%0 Report %A Galby, Esther %A Marx, D&#225;niel %A Schepper, Philipp %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Domination and Cut Problems on Chordal Graphs with Bounded Leafage : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1DF6-F %U https://arxiv.org/abs/2208.02850 %D 2022 %X The leafage of a chordal graph G is the minimum integer l such that G can be<br>realized as an intersection graph of subtrees of a tree with l leaves. We<br>consider structural parameterization by the leafage of classical domination and<br>cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018,<br>Algorithmica 2020] proved, among other things, that Dominating Set on chordal<br>graphs admits an algorithm running in time $2^{O(l^2)} n^{O(1)}$. We present a<br>conceptually much simpler algorithm that runs in time $2^{O(l)} n^{O(1)}$. We<br>extend our approach to obtain similar results for Connected Dominating Set and<br>Steiner Tree. We then consider the two classical cut problems MultiCut with<br>Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove<br>that the former is W[1]-hard when parameterized by the leafage and complement<br>this result by presenting a simple $n^{O(l)}$-time algorithm. To our surprise,<br>we find that Multiway Cut with Undeletable Terminals on chordal graphs can be<br>solved, in contrast, in $n^{O(1)}$-time.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC,

%0 Report %A Galby, Esther %A Khazaliya, Liana %A Inerney, Fionn Mc %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1DDF-A %U https://arxiv.org/abs/2206.15424 %D 2022 %X For a graph $G$, a subset $S \subseteq V(G)$ is called a \emph{resolving set}<br>if for any two vertices $u,v \in V(G)$, there exists a vertex $w \in S$ such<br>that $d(w,u) \neq d(w,v)$. The {\sc Metric Dimension} problem takes as input a<br>graph $G$ and a positive integer $k$, and asks whether there exists a resolving<br>set of size at most $k$. This problem was introduced in the 1970s and is known<br>to be NP-hard~[GT~61 in Garey and Johnson's book]. In the realm of<br>parameterized complexity, Hartung and Nichterlein~[CCC~2013] proved that the<br>problem is W[2]-hard when parameterized by the natural parameter $k$. They also<br>observed that it is FPT when parameterized by the vertex cover number and asked<br>about its complexity under \emph{smaller} parameters, in particular the<br>feedback vertex set number. We answer this question by proving that {\sc Metric<br>Dimension} is W[1]-hard when parameterized by the feedback vertex set number.<br>This also improves the result of Bonnet and Purohit~[IPEC 2019] which states<br>that the problem is W[1]-hard parameterized by the treewidth. Regarding the<br>parameterization by the vertex cover number, we prove that {\sc Metric<br>Dimension} does not admit a polynomial kernel under this parameterization<br>unless $NP\subseteq coNP/poly$. We observe that a similar result holds when the<br>parameter is the distance to clique. On the positive side, we show that {\sc<br>Metric Dimension} is FPT when parameterized by either the distance to cluster<br>or the distance to co-cluster, both of which are smaller parameters than the<br>vertex cover number.<br> %K Computer Science, Discrete Mathematics, cs.DM,Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Galby, Esther %A Kisfaludi-Bak, S&#225;ndor %A Marx, D&#225;niel %A Sharma, Roohani %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1E72-3 %U https://arxiv.org/abs/2208.06015 %D 2022 %X In the Directed Steiner Network problem, the input is a directed graph G, a<br>subset T of k vertices of G called the terminals, and a demand graph D on T.<br>The task is to find a subgraph H of G with the minimum number of edges such<br>that for every edge (s,t) in D, the solution H contains a directed s to t path.<br>In this paper we investigate how the complexity of the problem depends on the<br>demand pattern when G is planar. Formally, if \mathcal{D} is a class of<br>directed graphs closed under identification of vertices, then the<br>\mathcal{D}-Steiner Network (\mathcal{D}-SN) problem is the special case where<br>the demand graph D is restricted to be from \mathcal{D}. For general graphs,<br>Feldmann and Marx [ICALP 2016] characterized those families of demand graphs<br>where the problem is fixed-parameter tractable (FPT) parameterized by the<br>number k of terminals. They showed that if \mathcal{D} is a superset of one of<br>the five hard families, then \mathcal{D}-SN is W[1]-hard parameterized by k,<br>otherwise it can be solved in time f(k)n^{O(1)}.<br> For planar graphs an interesting question is whether the W[1]-hard cases can<br>be solved by subexponential parameterized algorithms. Chitnis et al. [SICOMP<br>2020] showed that, assuming the ETH, there is no f(k)n^{o(k)} time algorithm<br>for the general \mathcal{D}-SN problem on planar graphs, but the special case<br>called Strongly Connected Steiner Subgraph can be solved in time f(k)<br>n^{O(\sqrt{k})} on planar graphs. We present a far-reaching generalization and<br>unification of these two results: we give a complete characterization of the<br>behavior of every $\mathcal{D}$-SN problem on planar graphs. We show that<br>assuming ETH, either the problem is (1) solvable in time 2^{O(k)}n^{O(1)}, and<br>not in time 2^{o(k)}n^{O(1)}, or (2) solvable in time f(k)n^{O(\sqrt{k})}, but<br>not in time f(k)n^{o(\sqrt{k})}, or (3) solvable in time f(k)n^{O(k)}, but not<br>in time f(k)n^{o({k})}.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC,

%0 Report %A Gao, Yuan %A Kamkari, Hamidreza %A Karrenbauer, Andreas %A Mehlhorn, Kurt %A Sharifi, Mohammadamin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Physarum Inspired Dynamics to Solve Semi-Definite Programs : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B656-9 %U https://arxiv.org/abs/2111.02291 %D 2022 %X Physarum Polycephalum is a Slime mold that can solve the shortest path<br>problem. A mathematical model based on the Physarum's behavior, known as the<br>Physarum Directed Dynamics, can solve positive linear programs. In this paper,<br>we will propose a Physarum based dynamic based on the previous work and<br>introduce a new way to solve positive Semi-Definite Programming (SDP) problems,<br>which are more general than positive linear programs. Empirical results suggest<br>that this extension of the dynamic can solve the positive SDP showing that the<br>nature-inspired algorithm can solve one of the hardest problems in the<br>polynomial domain. In this work, we will formulate an accurate algorithm to<br>solve positive and some non-negative SDPs and formally prove some key<br>characteristics of this solver thus inspiring future work to try and refine<br>this method.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Optimization and Control, math.OC

%0 Conference Proceedings %A Giliberti, Jeff %A Karrenbauer, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improved Online Algorithm for Fractional Knapsack in the Random Order Model : %G eng %U http://hdl.handle.net/21.11116/0000-000C-11BF-A %R 10.1007/978-3-030-92702-8_12 %D 2022 %B 19th Workshop on Approximation and Online Algorithms %Z date of event: 2021-09-06 - 2021-09-10 %C Lisbon, Portugal %B Approximation and Online Algorithms %E Koenemann, Jochen; Preis, Britta %P 188 - 205 %I Springer %@ 978-3-030-92701-1 %B Lecture Notes in Computer Science %N 12982

%0 Conference Proceedings %A Goldenberg, Elazar %A Kociumaka, Tomasz %A Krauthgamer, Robert %A Saha, Barna %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1578-6 %R 10.1109/FOCS54457.2022.00070 %D 2022 %B IEEE 63rd Annual Symposium on Foundations of Computer Science %Z date of event: 2022-10-31 - 2022-11-03 %C Denver, CO, USA %B FOCS 2022 %P 674 - 685 %I IEEE %@ 978-1-6654-5519-0

%0 Report %A Gouleakis, Themis %A Lakis, Konstantinos %A Shahkarami, Golnoosh %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Learning-Augmented Algorithms for Online TSP on the Line : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1FCC-D %U https://arxiv.org/abs/2206.00655 %D 2022 %X We study the online Traveling Salesman Problem (TSP) on the line augmented<br>with machine-learned predictions. In the classical problem, there is a stream<br>of requests released over time along the real line. The goal is to minimize the<br>makespan of the algorithm. We distinguish between the open variant and the<br>closed one, in which we additionally require the algorithm to return to the<br>origin after serving all requests. The state of the art is a $1.64$-competitive<br>algorithm and a $2.04$-competitive algorithm for the closed and open variants,<br>respectively \cite{Bjelde:1.64}. In both cases, a tight lower bound is known<br>\cite{Ausiello:1.75, Bjelde:1.64}.<br> In both variants, our primary prediction model involves predicted positions<br>of the requests. We introduce algorithms that (i) obtain a tight 1.5<br>competitive ratio for the closed variant and a 1.66 competitive ratio for the<br>open variant in the case of perfect predictions, (ii) are robust against<br>unbounded prediction error, and (iii) are smooth, i.e., their performance<br>degrades gracefully as the prediction error increases.<br> Moreover, we further investigate the learning-augmented setting in the open<br>variant by additionally considering a prediction for the last request served by<br>the optimal offline algorithm. Our algorithm for this enhanced setting obtains<br>a 1.33 competitive ratio with perfect predictions while also being smooth and<br>robust, beating the lower bound of 1.44 we show for our original prediction<br>setting for the open variant. Also, we provide a lower bound of 1.25 for this<br>enhanced setting.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Learning, cs.LG

%0 Report %A Gutowski, Grzegorz %A Mittelst&#228;dt, Florian %A Rutter, Ignaz %A Spoerhase, Joachim %A Wolff, Alexander %A Zink, Johannes %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Coloring Mixed and Directional Interval Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000C-269B-B %U https://arxiv.org/abs/2208.14250 %D 2022 %X A mixed graph has a set of vertices, a set of undirected egdes, and a set of<br>directed arcs. A proper coloring of a mixed graph $G$ is a function $c$ that<br>assigns to each vertex in $G$ a positive integer such that, for each edge $uv$<br>in $G$, $c(u) \ne c(v)$ and, for each arc $uv$ in $G$, $c(u) < c(v)$. For a<br>mixed graph $G$, the chromatic number $\chi(G)$ is the smallest number of<br>colors in any proper coloring of $G$. A directional interval graph is a mixed<br>graph whose vertices correspond to intervals on the real line. Such a graph has<br>an edge between every two intervals where one is contained in the other and an<br>arc between every two overlapping intervals, directed towards the interval that<br>starts and ends to the right.<br> Coloring such graphs has applications in routing edges in layered orthogonal<br>graph drawing according to the Sugiyama framework; the colors correspond to the<br>tracks for routing the edges. We show how to recognize directional interval<br>graphs, and how to compute their chromatic number efficiently. On the other<br>hand, for mixed interval graphs, i.e., graphs where two intersecting intervals<br>can be connected by an edge or by an arc in either direction arbitrarily, we<br>prove that computing the chromatic number is NP-hard.<br> %K Computer Science, Discrete Mathematics, cs.DM

%0 Journal Article %A Halperin, Dan %A Har-Peled, Sariel %A Mehlhorn, Kurt %A Oh, Eunjin %A Sharir, Micha %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Maximum-Level Vertex in an Arrangement of Lines : %G eng %U http://hdl.handle.net/21.11116/0000-0009-D020-7 %R 10.1007/s00454-021-00338-9 %7 2022 %D 2022 %J Discrete & Computational Geometry %V 67 %& 439 %P 439 - 461 %I Springer %C New York, NY %@ false %U https://rdcu.be/cFlQF

%0 Conference Proceedings %A Han, Insu %A Zandieh, Amir %A Lee, Jaehoon %A Novak, Roman %A Xiao, Lechao %A Karbasi, Amin %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Fast Neural Kernel Embeddings for General Activations : %G eng %U http://hdl.handle.net/21.11116/0000-000C-90F3-E %D 2022 %B 36th Conference on Neural Information Processing Systems %Z date of event: 2022-11-28 - 2022-12-09 %C New Orleans, LA, USA %B Advances in Neural Information Processing Systems 35 %E Koyejo, S.; Mohamed, S.; Agarwal, A.; Belgrave, D.; Cho, K.; Oh, A. %P 35657 - 35671 %I Curran Associates, Inc. %U https://openreview.net/pdf?id=yLilJ1vZgMe

%0 Conference Proceedings %A Han, Insu %A Zandieh, Amir %A Avron, Haim %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Random Gegenbauer Features for Scalable Kernel Methods : %G eng %U http://hdl.handle.net/21.11116/0000-000C-90FB-6 %U https://proceedings.mlr.press/v162/han22g.html %D 2022 %B 39th International Conference on Machine Learning %Z date of event: 2022-07-17 - 2022-07-23 %C Baltimore, MA, USA %B Proceedings of the 39th International Conference on Machine Learning %E Chaudhuri, Kamalika; Jegelka, Stefanie; Le, Song; Csaba, Szepesvari; Gang, Niu; Sabato, Sivan %P 8330 - 8358 %B Proceedings of the Machine Learning Research %N 162 %@ false

%0 Report %A Hatzel, Meike %A Jaffke, Lars %A Lima, Paloma T. %A Masa&#345;&#237;k, Tom&#225;&#353; %A Pilipczuk, Marcin %A Sharma, Roohani %A Sorge, Manuel %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-Augmentation : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1DE8-F %U https://arxiv.org/abs/2207.07425 %D 2022 %X We show fixed-parameter tractability of the Directed Multicut problem with<br>three terminal pairs (with a randomized algorithm). This problem, given a<br>directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$,<br>$(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most<br>$k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all<br>$s_2t_2$-paths, and all $s_3t_3$-paths. The parameterized complexity of this<br>case has been open since Chitnis, Cygan, Hajiaghayi, and Marx proved<br>fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012, and<br>Pilipczuk and Wahlstr\"{o}m proved the W[1]-hardness of the 4-terminal-pairs<br>case at SODA 2016.<br> On the technical side, we use two recent developments in parameterized<br>algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch,<br>Pilipczuk, Wahlstr\"{o}m, STOC 2022] we cast the problem as a CSP problem with<br>few variables and constraints over a large ordered domain.We observe that this<br>problem can be in turn encoded as an FO model-checking task over a structure<br>consisting of a few 0-1 matrices. We look at this problem through the lenses of<br>twin-width, a recently introduced structural parameter [Bonnet, Kim,<br>Thomass\'{e}, Watrigant, FOCS 2020]: By a recent characterization [Bonnet,<br>Giocanti, Ossona de Mendes, Simon, Thomass\'{e}, Toru\'{n}czyk, STOC 2022] the<br>said FO model-checking task can be done in FPT time if the said matrices have<br>bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If<br>any of the matrices in the said encoding has a large grid minor, a vertex<br>corresponding to the ``middle'' box in the grid minor can be proclaimed<br>irrelevant -- not contained in the sought solution -- and thus reduced.<br> %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Jaffke, Lars %A Lima, Paloma T. %A Sharma, Roohani %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T b-Coloring Parameterized by Pathwidth is XNLP-complete : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1E7E-7 %U https://arxiv.org/abs/2209.07772 %D 2022 %X We show that the $b$-Coloring problem is complete for the class XNLP when<br>parameterized by the pathwidth of the input graph. Besides determining the<br>precise parameterized complexity of this problem, this implies that b-Coloring<br>parameterized by pathwidth is $W[t]$-hard for all $t$, and resolves the<br>parameterized complexity of $b$-Coloring parameterized by treewidth.<br> %K Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Jiang, Yonggang %A Zheng, Chaodong %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Robust and Optimal Contention Resolution without Collision Detection : %G eng %U http://hdl.handle.net/21.11116/0000-000C-104C-D %R 10.1145/3490148.3538592 %D 2022 %B 34th ACM Symposium on Parallelism in Algorithms and Architectures %Z date of event: 2022-07-11 - 2022-07-14 %C Philadelphia, PA, USA %B SPAA '22 %E Agrawal, Kunal; Lee, I-Ting Angelina %P 107 - 118 %I ACM %@ 978-1-4503-9146-7

%0 Report %A Kim, Eun Jung %A Masa&#345;&#237;k, Tom&#225;&#353; %A Pilipczuk, Marcin %A Sharma, Roohani %A Wahlstr&#246;m, Magnus %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On Weighted Graph Separation Problems and Flow-Augmentation : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1E78-D %U https://arxiv.org/abs/2208.14841 %D 2022 %X One of the first application of the recently introduced technique of<br>\emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm<br>for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark<br>problem in parameterized complexity. In this note we explore applicability of<br>flow-augmentation to other weighted graph separation problems parameterized by<br>the size of the cutset. We show the following. -- In weighted undirected graphs<br>\textsc{Multicut} is FPT, both in the edge- and vertex-deletion version. -- The<br>weighted version of \textsc{Group Feedback Vertex Set} is FPT, even with an<br>oracle access to group operations. -- The weighted version of \textsc{Directed<br>Subset Feedback Vertex Set} is FPT. Our study reveals \textsc{Directed<br>Symmetric Multicut} as the next important graph separation problem whose<br>parameterized complexity remains unknown, even in the unweighted setting.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC,

%0 Thesis %A Kinali-Dogan, Attila %Y Lenzen, Christoph %A referee: Mehlhorn, Kurt %A referee: Vernotte, Francoise %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On Time, Time Synchronization and Noise in Time Measurement Systems : %G eng %U http://hdl.handle.net/21.11116/0000-000B-5436-A %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2022 %P 140 p. %V phd %9 phd

%0 Journal Article %A Kirkpatrick, David %A Simon, Hans U. %A Zilles, Sandra %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Optimal Collusion-Free Teaching : %G eng %U http://hdl.handle.net/21.11116/0000-000C-332F-7 %D 2022 %X Formal models of learning from teachers need to respect certain criteria to<br>avoid collusion. The most commonly accepted notion of collusion-freeness was<br>proposed by Goldman and Mathias (1996), and various teaching models obeying<br>their criterion have been studied. For each model $M$ and each concept class<br>$\mathcal{C}$, a parameter $M$-$\mathrm{TD}(\mathcal{C})$ refers to the<br>teaching dimension of concept class $\mathcal{C}$ in model $M$---defined to be<br>the number of examples required for teaching a concept, in the worst case over<br>all concepts in $\mathcal{C}$.<br> This paper introduces a new model of teaching, called no-clash teaching,<br>together with the corresponding parameter $\mathrm{NCTD}(\mathcal{C})$.<br>No-clash teaching is provably optimal in the strong sense that, given any<br>concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's<br>collusion-freeness criterion, one obtains $\mathrm{NCTD}(\mathcal{C})\le<br>M$-$\mathrm{TD}(\mathcal{C})$. We also study a corresponding notion<br>$\mathrm{NCTD}^+$ for the case of learning from positive data only, establish<br>useful bounds on $\mathrm{NCTD}$ and $\mathrm{NCTD}^+$, and discuss relations<br>of these parameters to the VC-dimension and to sample compression.<br> In addition to formulating an optimal model of collusion-free teaching, our<br>main results are on the computational complexity of deciding whether<br>$\mathrm{NCTD}^+(\mathcal{C})=k$ (or $\mathrm{NCTD}(\mathcal{C})=k$) for given<br>$\mathcal{C}$ and $k$. We show some such decision problems to be equivalent to<br>the existence question for certain constrained matchings in bipartite graphs.<br>Our NP-hardness results for the latter are of independent interest in the study<br>of constrained graph matchings.<br> %K Computer Science, Learning, cs.LG,Statistics, Machine Learning, stat.ML %J Journal of Machine Learning Research %I JMLR.org %@ false

%0 Conference Proceedings %A Kisfaludi-Bak, S&#225;ndor %A Nederlof, Jesper %A W&#281;grzycki, Karol %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Gap-ETH-Tight Approximation Scheme for Euclidean TSP : %G eng %U http://hdl.handle.net/21.11116/0000-000A-C557-6 %R 10.1109/FOCS52979.2021.00043 %D 2022 %B IEEE 62nd Annual Symposium on Foundations of Computer Science %Z date of event: 2022-02-07 - 2022-02-10 %C Denver, CO, USA (Virtual Conference) %B FOCS 2021 %P 351 - 362 %I IEEE %@ 978-1-6654-2055-6

%0 Conference Proceedings %A Kociumaka, Tomasz %A Navarro, Gonzalo %A Olivares, Francisco %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Near-Optimal Search Time in &#948;-Optimal Space : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1534-2 %R 10.1007/978-3-031-20624-5_6 %D 2022 %B 5th Latin American Theoretical Informatics Symposium %Z date of event: 2022-11-07 - 2022-11-11 %C Guanajuato, Mexico %B LATIN 2022: Theoretical Informatics %E Casta&#241;eda, Armando; Rodr&#237;guez-Henr&#237;quez, Francisco %P 88 - 103 %I Springer %@ 978-3-031-20623-8 %B Lecture Notes in Computer Science %N 13568 %U https://rdcu.be/c19vn

%0 Journal Article %A Kociumaka, Tomasz %A Navarro, Gonzalo %A Prezza, Nicola %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Toward a Definitive Compressibility Measure for Repetitive Sequences : %G eng %U http://hdl.handle.net/21.11116/0000-000C-150A-2 %R 10.1109/TIT.2022.3224382 %7 2022 %D 2022 %J IEEE Transactions on Information Theory %V 69 %N 4 %& 2074 %P 2074 - 2092 %I IEEE %C Piscataway, NJ %@ false

%0 Conference Proceedings %A Krithika, R. %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Complexity of Contracting Bipartite Graphs into Small Cycles : %G eng %U http://hdl.handle.net/21.11116/0000-000B-5928-5 %R 10.1007/978-3-031-15914-5_26 %D 2022 %B 48th International Workshop on Graph-Theoretic Concepts in Computer Science %Z date of event: 2022-06-22 - 2022-06-24 %C T&#252;bingen, Germany %B Graph-Theoretic Concepts in Computer Science %E Bekos, Michael A.; Kaufmann, Michael %P 356 - 369 %I Springer %@ 978-3-031-15913-8 %B Lecture Notes in Computer Science %N 13453

%0 Report %A Krithika, R. %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Complexity of Contracting Bipartite Graphs into Small Cycles : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1DCB-0 %U https://arxiv.org/abs/2206.07358 %D 2022 %X For a positive integer $\ell \geq 3$, the $C_\ell$-Contractibility problem<br>takes as input an undirected simple graph $G$ and determines whether $G$ can be<br>transformed into a graph isomorphic to $C_\ell$ (the induced cycle on $\ell$<br>vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed<br>that $C_4$-Contractibility is NP-complete in general graphs. It is easy to<br>verify that $C_3$-Contractibility is polynomial-time solvable. Dabrowski and<br>Paulusma [IPL 2017] showed that $C_{\ell}$-Contractibility is \NP-complete\ on<br>bipartite graphs for $\ell = 6$ and posed as open problems the status of the<br>problem when $\ell$ is 4 or 5. In this paper, we show that both<br>$C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite<br>graphs.<br> %K Computer Science, Computational Complexity, cs.CC

%0 Conference Proceedings %A K&#252;nnemann, Marvin %A Nusser, Andr&#233; %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1F8F-2 %R 10.1137/1.9781611977073 %D 2022 %B Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2022-01-09 - 2022-01-12 %C Virtual %B Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms %E Naor, Seffi; Buchbinder, Niv %P 3181 - 3201 %I SIAM %@ 978-1-61197-707-3

%0 Conference Proceedings %A Mansouri, Farnam %A Simon, Hans U. %A Singla, Adish %A Zilles, Sandra %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T On Batch Teaching with Sample Complexity Bounded by VCD : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1601-A %D 2022 %B 36th Conference on Neural Information Processing Systems %Z date of event: 2022-11-28 - 2022-12-09 %C New Orleans, LA, USA %B Advances in Neural Information Processing Systems 35 %E Koyejo, S.; Mohamed, S.; Agarwal, A.; Belgrave, D.; Cho, K.; Oh, A. %P 15732 - 15742 %I Curran Associates, Inc %U https://openreview.net/pdf?id=wKf5dRSartn

%0 Report %A Nederlof, Jesper %A Pilipczuk, Micha&#322; %A W&#281;grzycki, Karol %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Bounding Generalized Coloring Numbers of Planar Graphs Using Coin Models : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1EF3-1 %U https://arxiv.org/abs/2201.09340 %D 2022 %X We study Koebe orderings of planar graphs: vertex orderings obtained by<br>modelling the graph as the intersection graph of pairwise internally-disjoint<br>discs in the plane, and ordering the vertices by non-increasing radii of the<br>associated discs. We prove that for every $d\in \mathbb{N}$, any such ordering<br>has $d$-admissibility bounded by $O(d/\ln d)$ and weak $d$-coloring number<br>bounded by $O(d^4 \ln d)$. This in particular shows that the $d$-admissibility<br>of planar graphs is bounded by $O(d/\ln d)$, which asymptotically matches a<br>known lower bound due to Dvo\v{r}\'ak and Siebertz.<br> %K Mathematics, Combinatorics, math.CO,Computer Science, Discrete Mathematics, cs.DM

%0 Conference Proceedings %A Nederlof, Jesper %A Pilipczuk, Micha&#322; %A Swennenhuis, C&#233;line M. F. %A W&#281;grzycki, Karol %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Isolation Schemes for Problems on Decomposable Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1EEC-A %R 10.4230/LIPIcs.STACS.2022.50 %U urn:nbn:de:0030-drops-158601 %D 2022 %B 39th International Symposium on Theoretical Aspects of Computer Science %Z date of event: 2022-03-15 - 2022-03-18 %C Marseille, France (Virtual Conference) %B 39th International Symposium on Theoretical Aspects of Computer Science %E Berenbrink, Petra; Monmege, Benjamin %P 1 - 20 %Z sequence number: 50 %I Schloss Dagstuhl %@ 978-3-95977-222-8 %B Leibniz International Proceedings in Informatics %N 219 %@ false

%0 Report %A Nederlof, Jesper %A Swennenhuis, C&#233;line M. F. %A W&#281;grzycki, Karol %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995n) time : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1F35-7 %U https://arxiv.org/abs/2208.02664 %D 2022 %X In a classical scheduling problem, we are given a set of $n$ jobs of unit<br>length along with precedence constraints and the goal is to find a schedule of<br>these jobs on $m$ identical machines that minimizes the makespan. This problem<br>is well-known to be NP-hard for an unbounded number of machines. Using standard<br>3-field notation, it is known as $P|\text{prec}, p_j=1|C_{\max}$.<br> We present an algorithm for this problem that runs in $O(1.995^n)$ time.<br>Before our work, even for $m=3$ machines the best known algorithms ran in<br>$O^\ast(2^n)$ time. In contrast, our algorithm works when the number of<br>machines $m$ is unbounded. A crucial ingredient of our approach is an algorithm<br>with a runtime that is only single-exponential in the vertex cover of the<br>comparability graph of the precedence constraint graph. This heavily relies on<br>insights from a classical result by Dolev and Warmuth (Journal of Algorithms<br>1984) for precedence graphs without long chains.<br> %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Thesis %A Nusser, Andr&#233; %Y Bringmann, Karl %A referee: Mehlhorn, Kurt %A referee: Chan, Timothy %A referee: de Ber, Mark %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Fine-Grained Complexity and Algorithm Engineering of Geometric Similarity Measures : %G eng %U http://hdl.handle.net/21.11116/0000-000C-2693-3 %R 10.22028/D291-37018 %U urn:nbn:de:bsz:291--ds-370184 %F OTHER: hdl:20.500.11880/33904 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2022 %P XIV, 210 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/33904

%0 Journal Article %A Ray Chaudhury, Bhaskar %A Cheung, Yun Kuen %A Garg, Jugal %A Garg, Naveen %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fair Division of Indivisible Goods for a Class of Concave Valuations : %G eng %U http://hdl.handle.net/21.11116/0000-000A-9DB8-6 %R 10.1613/jair.1.12911 %7 2022 %D 2022 %J Journal of Artificial Intelligence Research %V 74 %& 111 %P 111 - 142 %I AI Access Foundation %C S.l. %@ false

%0 Journal Article %A Roth, Marc %A Schmitt, Johannes %A Wellnitz, Philip %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting Small Induced Subgraphs Satisfying Monotone Properties : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1EB6-6 %R 10.1137/20M1365624 %7 2022 %D 2022 %J SIAM Journal on Computing %& FOCS20-139 %P FOCS20-139 - FOCS20-174 %I SIAM %C Philadelphia, PA %@ false

%0 Thesis %A Wiederhake, Ben %Y Lenzen, Christoph %A referee: Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Pulse Propagation, Graph Cover, and Packet Forwarding : %G eng %U http://hdl.handle.net/21.11116/0000-000A-CEBE-9 %R 10.22028/D291-36608 %U nbn:de:bsz:291--ds-366085 %F OTHER: hdl:20.500.11880/33316 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2022 %P 83 p. %V phd %9 phd %X We study distributed systems, with a particular focus on graph problems and fault<br>tolerance.<br>Fault-tolerance in a microprocessor or even System-on-Chip can be improved by using<br>a fault-tolerant pulse propagation design. The existing design TRIX achieves this goal<br>by being a distributed system consisting of very simple nodes. We show that even in<br>the typical mode of operation without faults, TRIX performs significantly better than a<br>regular wire or clock tree: Statistical evaluation of our simulated experiments show that<br>we achieve a skew with standard deviation of O(log log H), where H is the height of the<br>TRIX grid.<br>The distance-r generalization of classic graph problems can give us insights on how<br>distance affects hardness of a problem. For the distance-r dominating set problem, we<br>present both an algorithmic upper and unconditional lower bound for any graph class<br>with certain high-girth and sparseness criteria. In particular, our algorithm achieves a<br>O(r &#183; f(r))-approximation in time O(r), where f is the expansion function, which correlates<br>with density. For constant r, this implies a constant approximation factor, in constant<br>time. We also show that no algorithm can achieve a (2r + 1 &#8722; &#948;)-approximation for any<br>&#948; > 0 in time O(r), not even on the class of cycles of girth at least 5r. Furthermore, we<br>extend the algorithm to related graph cover problems and even to a different execution<br>model.<br>Furthermore, we investigate the problem of packet forwarding, which addresses the<br>question of how and when best to forward packets in a distributed system. These packets<br>are injected by an adversary. We build on the existing algorithm OED to handle more<br>than a single destination. In particular, we show that buffers of size O(log n) are sufficient<br>for this algorithm, in contrast to O(n) for the naive approach. %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/33316

%0 Conference Proceedings %A Woodruff, David %A Zandieh, Amir %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time : %G eng %U http://hdl.handle.net/21.11116/0000-000C-9101-E %U https://proceedings.mlr.press/v162/woodruff22a.html %D 2022 %B 39th International Conference on Machine Learning %Z date of event: 2022-07-17 - 2022-07-23 %C Baltimore, MA, USA %B Proceedings of the 39th International Conference on Machine Learning %E Chaudhuri, Kamalika; Jegelka, Stefanie; Le, Song; Csaba, Szepesvari; Gang, Niu; Sabato, Sivan %P 23933 - 23964 %B Proceedings of the Machine Learning Research %N 162 %@ false

%0 Report %A Zandieh, Amir %A Han, Insu %A Avron, Haim %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Near Optimal Reconstruction of Spherical Harmonic Expansions : %G eng %U http://hdl.handle.net/21.11116/0000-000C-9105-A %U https://arxiv.org/abs/2202.12995 %D 2022 %X We propose an algorithm for robust recovery of the spherical harmonic<br>expansion of functions defined on the d-dimensional unit sphere<br>$\mathbb{S}^{d-1}$ using a near-optimal number of function evaluations. We show<br>that for any $f \in L^2(\mathbb{S}^{d-1})$, the number of evaluations of $f$<br>needed to recover its degree-$q$ spherical harmonic expansion equals the<br>dimension of the space of spherical harmonics of degree at most $q$ up to a<br>logarithmic factor. Moreover, we develop a simple yet efficient algorithm to<br>recover degree-$q$ expansion of $f$ by only evaluating the function on<br>uniformly sampled points on $\mathbb{S}^{d-1}$. Our algorithm is based on the<br>connections between spherical harmonics and Gegenbauer polynomials and leverage<br>score sampling methods. Unlike the prior results on fast spherical harmonic<br>transform, our proposed algorithm works efficiently using a nearly optimal<br>number of samples in any dimension d. We further illustrate the empirical<br>performance of our algorithm on numerical examples.<br> %K Mathematics, Numerical Analysis, math.NA,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Learning, cs.LG,Computer Science, Numerical Analysis, cs.NA,eess.SP