mehlhorn

%0 Conference Proceedings %A Afshinmehr, Mahyar %A Danaei, Alireza %A Kazemi, Mehrafarin %A Mehlhorn, Kurt %A Rathi, Nidhi %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T EFX Allocations and Orientations on Bipartite Multi-Graphs: A Complete Picture : %G eng %U http://hdl.handle.net/21.11116/0000-0010-6A9E-6 %D 2024 %B 24th International Conference on Autonomous Agents and Multiagent Systems %Z date of event: 2025-05-19 - 2025-05-23 %C Detroit, MI, USA %X We consider the problem of selecting a committee of $k$ alternatives among<br>$m$ alternatives, based on the ordinal rank list of voters. Our focus is on the<br>case where both voters and alternatives lie on a metric space-specifically, on<br>the line-and the objective is to minimize the additive social cost. The<br>additive social cost is the sum of the costs for all voters, where the cost for<br>each voter is defined as the sum of their distances to each member of the<br>selected committee.<br> We propose a new voting rule, the Polar Comparison Rule, which achieves upper<br>bounds of $1 + \sqrt{2} \approx 2.41$ and $7/3 \approx 2.33$ distortions for $k<br>= 2$ and $k = 3$, respectively, and we show that these bounds are tight.<br>Furthermore, we generalize this rule, showing that it maintains a distortion of<br>roughly $7/3$ based on the remainder of the committee size when divided by<br>three. We also establish lower bounds on the achievable distortion based on the<br>parity of $k$ and for both small and large committee sizes.<br> %K Computer Science, Computer Science and Game Theory, cs.GT %B Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems %I ACM

%0 Conference Proceedings %A Caragiannis, Ioannis %A Mehlhorn, Kurt %A Rathi, Nidhi %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity : %G eng %U http://hdl.handle.net/21.11116/0000-0010-6AE0-A %D 2025 %B The 39th Annual AAAI Conference on Artificial Intelligence %Z date of event: 2025-03-25 - 2025-04-04 %C Philadelphia, PA, USA %B Proceedings of the 39th AAAI Conference on Artificial Intelligence %I AAAI

%0 Journal Article %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: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-0010-2CEB-5 %R 10.1287/opre.2023.0433 %7 2024-10-21 %D 2024 %J Operations Research %& 1 %P 1 - 14 %I informs %C Catonsville, MD %@ false

%0 Journal Article %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 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 External Organizations External Organizations %T Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability : %G eng %U http://hdl.handle.net/21.11116/0000-0010-5EA7-9 %D 2024 %X We study the problem of allocating a set of indivisible goods among a set of<br>agents with \emph{2-value additive valuations}. In this setting, each good is<br>valued either $1$ or $\sfrac{p}{q}$, for some fixed co-prime numbers $p,q\in<br>\NN$ such that $1\leq q < p$. Our goal is to find an allocation maximizing the<br>\emph{Nash social welfare} (\NSW), i.e., the geometric mean of the valuations<br>of the agents. In this work, we give a complete characterization of<br>polynomial-time tractability of \NSW\ maximization that solely depends on the<br>values of $q$.<br> We start by providing a rather simple polynomial-time algorithm to find a<br>maximum \NSW\ allocation when the valuation functions are \emph{integral}, that<br>is, $q=1$. We then exploit more involved techniques to get an algorithm<br>producing a maximum \NSW\ allocation for the \emph{half-integral} case, that<br>is, $q=2$. Finally, we show it is \classNP-hard to compute an allocation with<br>maximum \NSW\ whenever $q\geq3$.<br> %K Computer Science, Computer Science and Game Theory, cs.GT %J Mathematics of Operations Research %@ false

%0 Journal Article %A Folz, Frederic %A Mehlhorn, Kurt %A Morigi, Giovanna %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Self-organized Transport in Noisy Dynamic Networks : %G eng %U http://hdl.handle.net/21.11116/0000-0010-2CF2-C %R 10.1103/PhysRevE.110.044310 %7 2024-10-21 %D 2024 %J Physical Review E %O Phys. Rev. E %V 110 %N 4 %Z sequence number: 044310 %I American Physical Society %C Melville, NY %@ false

%0 Journal Article %A Garg, Jugal %A Hoefer, Martin %A 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 Satiation in Fisher Markets and Approximation of Nash Social Welfare : %G eng %U http://hdl.handle.net/21.11116/0000-000D-944A-9 %R 10.1287/moor.2019.0129 %7 2023-07-18 %D 2024 %J Mathematics of Operations Research %V 49 %N 2 %& 1109 %P 1109 - 1139 %I Institute for Operations Research and the Manageme %@ false

%0 Journal Article %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T EFX Exists for Three Agents : %G eng %U http://hdl.handle.net/21.11116/0000-000E-6961-F %R 10.1145/3616009 %D 2024 %J Journal of the ACM %V 71 %N 1 %& 1 %P 1 - 27 %Z sequence number: 4 %I ACM %C New York, NY %@ false

%0 Journal Article %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %A Mehta, Ruta %A Misra, Pranabendu %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-000E-0D04-0 %R 10.1287/moor.2021.0252 %7 2023-11-22 %D 2024 %J Mathematics of Operations Research %V 49 %N 4 %& 2323 %P 2323 - 2340 %I Institute for Operations Research and the Manageme %@ false

%0 Conference Proceedings %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: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-000F-1437-D %R 10.1145/3580507.3597799 %D 2023 %B 24th ACM Conference on Economics and Computation %Z date of event: 2023-07-09 - 2023-07-12 %C London, UK %B EC 2023 %P 61 - 61 %I ACM %@ 979-8-4007-0104-7

%0 Conference Proceedings %A Akrami, Hannaneh %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 Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Fair and Efficient Allocation of Indivisible Chores with Surplus : %G eng %U http://hdl.handle.net/21.11116/0000-000F-1425-1 %R 10.24963/ijcai.2023/277 %D 2023 %B Thirty-Second International Joint Conference on Artificial Intelligence %Z date of event: 2023-08-19 - 2023-08-25 %C Macao %B Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence %E Elkind, Edith %P 2494 - 2502 %I IJCAI %@ 978-1-956792-03-4 %U https://www.ijcai.org/proceedings/2023/277

%0 Conference Proceedings %A Akrami, Hannaneh %A Mehlhorn, Kurt %A Seddighin, Masoud %A Shahkarami, Golnoosh %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations : %G eng %U http://hdl.handle.net/21.11116/0000-000F-1435-F %D 2023 %B Thirty-seventh Annual Conference on Neural Information Processing Systems %Z date of event: 2023-12-10 - 2023-12-16 %C New Orleans, LA, USA %B Advances in Neural Information Processing Systems 36 %E Oh, A.; Neumann, T.; Globerson, A.; Saenko, K.; Hartdt, M.; Levine, S. %P 58821 - 58832 %I Curran Associates, Inc %U https://proceedings.neurips.cc/paper_files/paper/2023/file/b7ed46bd87cd51d4c031b96d9b1a8eb6-Paper-Conference.pdf

%0 Journal Article %A Folz, Frederic %A Mehlhorn, Kurt %A Morigi, Giovanna %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Noise-Induced Network Topologies : %G eng %U http://hdl.handle.net/21.11116/0000-0010-2CE4-C %R 10.1103/PhysRevLett.130.267401 %7 2023-06-30 %D 2023 %J Physical Review Letters %O Phys. Rev. Lett. %V 130 %N 26 %Z sequence number: 267401 %I American Physical Society %C Woodbury, N.Y. %@ 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 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 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 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 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 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society 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-2000-F %U https://arxiv.org/abs/2107.08965 %D 2021 %X We consider the problem of maximizing the Nash social welfare when allocating<br>a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We<br>study instances, in which all agents have 2-value additive valuations: The<br>value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is<br>$v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly,<br>we design an algorithm to compute an optimal allocation in polynomial time if<br>$p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate<br>scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p<br>\ge 3$.<br> In terms of approximation, we present positive and negative results for<br>general $p$ and $q$. We show that our algorithm obtains an approximation ratio<br>of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with<br>a lower bound of $1.000015$ achieved at $p/q = 4/5$.<br> %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Report %A Akrami, Hannaneh %A Ray Chaudhury, Bhaskar %A Mehlhorn, Kurt %A Shahkarami, Golnoosh %A Vermande, Quentin %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Nash Social Welfare for 2-value Instances : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB45-4 %U https://arxiv.org/abs/2106.14816 %D 2021 %X We study the problem of allocating a set of indivisible goods among agents<br>with 2-value additive valuations. Our goal is to find an allocation with<br>maximum Nash social welfare, i.e., the geometric mean of the valuations of the<br>agents. We give a polynomial-time algorithm to find a Nash social welfare<br>maximizing allocation when the valuation functions are integrally 2-valued,<br>i.e., each agent has a value either $1$ or $p$ for each good, for some positive<br>integer $p$. We then extend our algorithm to find a better approximation factor<br>for general 2-value instances.<br> %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Conference Proceedings %A Chaudhury, Bhaskar Ray %A Garg, Jugal %A Mehlhorn, Kurt %A Mehta, Ruta %A Misra, Pranabendu %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improving EFX Guarantees through Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B3F6-7 %R 10.1145/3465456.3467605 %D 2021 %B 22nd ACM Conference on Economics and Computation %Z date of event: 2021-07-18 - 2021-07-23 %C Budapest, Hungary (Virtual) %B EC '21 %E Bir&#243;, P&#233;ter; Chawla, Shuchi; Echenique, Federico; Sodomka, Eric %P 310 - 311 %I ACM %@ 978-1-4503-8554-1

%0 Journal Article %A Folz, Frederic %A Mehlhorn, Kurt %A Morigi, Giovanna %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Interplay of Periodic Dynamics and Noise: Insights from a Simple Adaptive System : %G eng %U http://hdl.handle.net/21.11116/0000-0009-9D3F-1 %R 10.1103/PhysRevE.104.054215 %7 2021 %D 2021 %J Physical Review E %O Phys. Rev. E %V 104 %N 5 %Z sequence number: 054215 %I American Physical Society %C Melville, NY %@ false

%0 Report %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %A Mehta, Ruta %A Misra, Pranabendu %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improving EFX Guarantees through Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB40-9 %U https://arxiv.org/abs/2103.01628 %D 2021 %X We study the problem of fairly allocating a set of indivisible goods among<br>$n$ agents with additive valuations. Envy-freeness up to any good (EFX) is<br>arguably the most compelling fairness notion in this context. However, the<br>existence of EFX allocations has not been settled and is one of the most<br>important problems in fair division. Towards resolving this problem, many<br>impressive results show the existence of its relaxations, e.g., the existence<br>of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated<br>goods. The latter result was recently improved for three agents, in which the<br>two unallocated goods are allocated through an involved procedure. Reducing the<br>number of unallocated goods for arbitrary number of agents is a systematic way<br>to settle the big question. In this paper, we develop a new approach, and show<br>that for every $\varepsilon \in (0,1/2]$, there always exists a<br>$(1-\varepsilon)$-EFX allocation with sublinear number of unallocated goods and<br>high Nash welfare.<br> For this, we reduce the EFX problem to a novel problem in extremal graph<br>theory. We introduce the notion of rainbow cycle number $R(\cdot)$. For all $d<br>\in \mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite<br>digraph $G =(\cup_{i \in [k]} V_i, E)$, in which<br> 1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for<br>all $i \in [k]$,<br> 2) for any two parts $V_i$ and $V_j$, each vertex in $V_i$ has an incoming<br>edge from some vertex in $V_j$ and vice-versa, and<br> 3) there exists no cycle in $G$ that contains at most one vertex from each<br>part.<br> We show that any upper bound on $R(d)$ directly translates to a sublinear<br>bound on the number of unallocated goods. We establish a polynomial upper bound<br>on $R(d)$, yielding our main result. Furthermore, our approach is constructive,<br>which also gives a polynomial-time algorithm for finding such an allocation.<br> %K Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Ray Chaudhury, Bhaskar %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Sgouritsa, Alkmini %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Little Charity Guarantees Almost Envy-Freeness : %G eng %U http://hdl.handle.net/21.11116/0000-0009-2B38-9 %R 10.1137/20M1359134 %7 2021 %D 2021 %J SIAM Journal on Computing %V 50 %N 4 %& 1336 %P 1336 - 1358 %I SIAM %C Philadelphia, PA %@ false

%0 Report %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 Multi-Commodity Flow Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-0007-2312-D %U https://arxiv.org/abs/2009.01498 %D 2020 %X In wet-lab experiments \cite{Nakagaki-Yamada-Toth,Tero-Takagi-etal}, the<br>slime mold Physarum polycephalum has demonstrated its ability to solve shortest<br>path problems and to design efficient networks, see Figure \ref{Wet-Lab<br>Experiments} for illustrations. Physarum polycephalum is a slime mold in the<br>Mycetozoa group. For the shortest path problem, a mathematical model for the<br>evolution of the slime was proposed in \cite{Tero-Kobayashi-Nakagaki} and its<br>biological relevance was argued. The model was shown to solve shortest path<br>problems, first in computer simulations and then by mathematical proof. It was<br>later shown that the slime mold dynamics can solve more general linear programs<br>and that many variants of the dynamics have similar convergence behavior. In<br>this paper, we introduce a dynamics for the network design problem. We<br>formulate network design as the problem of constructing a network that<br>efficiently supports a multi-commodity flow problem. We investigate the<br>dynamics in computer simulations and analytically. The simulations show that<br>the dynamics is able to construct efficient and elegant networks. In the<br>theoretical part we show that the dynamics minimizes an objective combining the<br>cost of the network and the cost of routing the demands through the network. We<br>also give alternative characterization of the optimum solution.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Neural and Evolutionary Computing, cs.NE

%0 Journal Article %A Facca, Enrico %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ 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 Convergence of the Non-Uniform Directed Physarum Model : %G eng %U http://hdl.handle.net/21.11116/0000-0006-97B9-F %R 10.1016/j.tcs.2020.01.034 %7 2020 %D 2020 %J Theoretical Computer Science %V 816 %& 184 %P 184 - 194 %I Elsevier %C Amsterdam %@ false

%0 Report %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-0006-AFB1-D %U http://arxiv.org/abs/2003.00518 %D 2020 %X Let $L$ be a set of $n$ lines in the plane, not necessarily in general<br>position. We present an efficient algorithm for finding all the vertices of the<br>arrangement $A(L)$ of maximum level, where the level of a vertex $v$ is the<br>number of lines of $L$ that pass strictly below $v$. The problem, posed in<br>Exercise~8.13 in de Berg etal [BCKO08], appears to be much harder than it<br>seems, as this vertex might not be on the upper envelope of the lines.<br> We first assume that all the lines of $L$ are distinct, and distinguish<br>between two cases, depending on whether or not the upper envelope of $L$<br>contains a bounded edge. In the former case, we show that the number of lines<br>of $L$ that pass above any maximum level vertex $v_0$ is only $O(\log n)$. In<br>the latter case, we establish a similar property that holds after we remove<br>some of the lines that are incident to the single vertex of the upper envelope.<br>We present algorithms that run, in both cases, in optimal $O(n\log n)$ time.<br> We then consider the case where the lines of $L$ are not necessarily<br>distinct. This setup is more challenging, and the best we have is an algorithm<br>that computes all the maximum-level vertices in time $O(n^{4/3}\log^{3}n)$.<br> Finally, we consider a related combinatorial question for degenerate<br>arrangements, where many lines may intersect in a single point, but all the<br>lines are distinct: We bound the complexity of the weighted $k$-level in such<br>an arrangement, where the weight of a vertex is the number of lines that pass<br>through the vertex. We show that the bound in this case is $O(n^{4/3})$, which<br>matches the corresponding bound for non-degenerate arrangements, and we use<br>this bound in the analysis of one of our algorithms.<br> %K Computer Science, Computational Geometry, cs.CG

%0 Journal Article %A Karrenbauer, Andreas %A Kolev, Pavel %A 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 Convergence of the Non-Uniform Physarum Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-0006-97C1-5 %R 10.1016/j.tcs.2020.02.032 %7 2020 %D 2020 %J Theoretical Computer Science %V 816 %& 260 %P 260 - 269 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A 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 EFX Exists for Three Agents : %G eng %U http://hdl.handle.net/21.11116/0000-0007-223A-2 %R 10.1145/3391403.3399511 %D 2020 %B 21st ACM Conference on Economics and Computation %Z date of event: 2020-07-13 - 2020-07-17 %C Virtual Event, Hungary %B EC '20 %E Bir&#243;, P&#233;ter; Hartline, Jason %P 1 - 19 %I ACM %@ 978-1-4503-7975-5

%0 Report %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A 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 EFX exists for three agents : %G eng %U http://hdl.handle.net/21.11116/0000-0006-AF99-9 %U http://arxiv.org/abs/2002.05119 %D 2020 %X We study the problem of distributing a set of indivisible items among agents<br>with additive valuations in a $\mathit{fair}$ manner. The fairness notion under<br>consideration is Envy-freeness up to any item (EFX). Despite significant<br>efforts by many researchers for several years, the existence of EFX allocations<br>has not been settled beyond the simple case of two agents. In this paper, we<br>show constructively that an EFX allocation always exists for three agents.<br>Furthermore, we falsify the conjecture by Caragiannis et al. by showing an<br>instance with three agents for which there is a partial EFX allocation (some<br>items are not allocated) with higher Nash welfare than that of any complete EFX<br>allocation.<br> %K Computer Science, Computer Science and Game Theory, cs.GT,

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Sgouritsa, Alkmini %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Little Charity Guarantees Almost Envy-Freeness : %G eng %U http://hdl.handle.net/21.11116/0000-0006-AF89-B %R 10.1137/1.9781611975994.162 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 2658 - 2672 %I SIAM %@ 978-1-61197-599-4

%0 Report %A Abdulaziz, Mohammad %A Mehlhorn, Kurt %A Nipkow, Tobias %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Trustworthy Graph Algorithms : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4FA8-6 %U http://arxiv.org/abs/1907.04065 %D 2019 %X The goal of the LEDA project was to build an easy-to-use and extendable<br>library of correct and efficient data structures, graph algorithms and<br>geometric algorithms. We report on the use of formal program verification to<br>achieve an even higher level of trustworthiness. Specifically, we report on an<br>ongoing and largely finished verification of the blossom-shrinking algorithm<br>for maximum cardinality matching.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Logic in Computer Science, cs.LO,Computer Science, Software Engineering, cs.SE

%0 Conference Proceedings %A Abdulaziz, Mohammad %A Mehlhorn, Kurt %A Nipkow, Tobias %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Trustworthy Graph Algorithms : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4F89-9 %R 10.4230/LIPIcs.MFCS.2019.1 %U urn:nbn:de:0030-drops-109456 %D 2019 %B 44th International Symposium on Mathematical Foundations of Computer Science %Z date of event: 2019-08-26 - 2019-08-30 %C Aachen, Germany %B 44th International Symposium on Mathematical Foundations of Computer Science %E Rossmanith, Peter; Heggernes, Pinar; Katoen, Joost-Pieter %Z sequence number: 1 %I Schloss Dagstuhl %@ 978-3-95977-117-7 %B Leibniz International Proceedings in Informatics %N 138 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2019/10945/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Journal Article %A Afshani, Peyman %A Agrawal, Manindra %A Doerr, Benjamin %A Doerr, Carola %A Larsen, Kasper Green %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Query Complexity of a Permutation-based Variant of Mastermind : %G eng %U http://hdl.handle.net/21.11116/0000-0002-FE83-C %R 10.1016/j.dam.2019.01.007 %7 2019 %D 2019 %J Discrete Applied Mathematics %V 260 %& 28 %P 28 - 50 %I North-Holland %C Amsterdam %@ false

%0 Report %A Akrami, Hannaneh %A Mehlhorn, Kurt %A Odland, Tommy %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Ratio-Balanced Maximum Flows : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B2FE-6 %U http://arxiv.org/abs/1902.11047 %D 2019 %X When a loan is approved for a person or company, the bank is subject to<br>\emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a<br>bank will require some form of \emph{security}, which will be collected if the<br>lender defaults. Accounts can be secured by several securities and a security<br>can be used for several accounts. The goal is to fractionally assign the<br>securities to the accounts so as to balance the risk.<br> This situation can be modelled by a bipartite graph. We have a set $S$ of<br>securities and a set $A$ of accounts. Each security has a \emph{value} $v_i$<br>and each account has an \emph{exposure} $e_j$. If a security $i$ can be used to<br>secure an account $j$, we have an edge from $i$ to $j$. Let $f_{ij}$ be part of<br>security $i$'s value used to secure account $j$. We are searching for a maximum<br>flow that send at most $v_i$ units out of node $i \in S$ and at most $e_j$<br>units into node $j \in A$. Then $s_j = e_j - \sum_i f_{ij}$ is the unsecured<br>part of account $j$. We are searching for the maximum flow that minimizes<br>$\sum_j s_j^2/e_j$.<br> %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Akrami, Hannaneh %A Mehlhorn, Kurt %A Odland, Tommy %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Ratio-Balanced Maximum Flows : %G eng %U http://hdl.handle.net/21.11116/0000-0004-8FF0-C %R 10.1016/j.ipl.2019.06.003 %7 2019 %D 2019 %J Information Processing Letters %V 150 %& 13 %P 13 - 17 %I Elsevier %@ false

%0 Journal Article %A Becker, Ruben %A Bonifaci, Vincenzo %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Two Results on Slime Mold Computations : %G eng %U http://hdl.handle.net/21.11116/0000-0002-A3AE-2 %R 10.1016/j.tcs.2018.08.027 %7 2018 %D 2019 %X In this paper, we present two results on slime mold computations. The first<br>one treats a biologically-grounded model, originally proposed by biologists<br>analyzing the behavior of the slime mold Physarum polycephalum. This primitive<br>organism was empirically shown by Nakagaki et al. to solve shortest path<br>problems in wet-lab experiments (Nature'00). We show that the proposed simple<br>mathematical model actually generalizes to a much wider class of problems,<br>namely undirected linear programs with a non-negative cost vector.<br> For our second result, we consider the discretization of a<br>biologically-inspired model. This model is a directed variant of the<br>biologically-grounded one and was never claimed to describe the behavior of a<br>biological system. Straszak and Vishnoi showed that it can<br>$\epsilon$-approximately solve flow problems (SODA'16) and even general linear<br>programs with positive cost vector (ITCS'16) within a finite number of steps.<br>We give a refined convergence analysis that improves the dependence on<br>$\epsilon$ from polynomial to logarithmic and simultaneously allows to choose a<br>step size that is independent of $\epsilon$. Furthermore, we show that the<br>dynamics can be initialized with a more general set of (infeasible) starting<br>points.<br> %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Dynamical Systems, math.DS,Mathematics, Optimization and Control, math.OC, Physics, Biological Physics, physics.bio-ph %J Theoretical Computer Science %V 773 %& 79 %P 79 - 106 %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Bei, Xiaohui %A Garg, Jugal %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Earning and Utility Limits in Fisher Markets : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4F7A-B %R 10.1145/3340234 %7 2019 %D 2019 %J ACM Transactions on Economics and Computation %O TEAC %V 7 %N 2 %Z sequence number: 10 %I ACM %C New York, NY

%0 Report %A Facca, Enrico %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ 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 Convergence of the Non-Uniform Directed Physarum Model : %G eng %U http://hdl.handle.net/21.11116/0000-0005-1DBA-A %U http://arxiv.org/abs/1906.07781 %D 2019 %X The directed Physarum dynamics is known to solve positive linear programs:<br>minimize $c^T x$ subject to $Ax = b$ and $x \ge 0$ for a positive cost vector<br>$c$. The directed Physarum dynamics evolves a positive vector $x$ according to<br>the dynamics $\dot{x} = q(x) - x$. Here $q(x)$ is the solution to $Af = b$ that<br>minimizes the "energy" $\sum_i c_i f_i^2/x_i$.<br> In this paper, we study the non-uniform directed dynamics $\dot{x} = D(q(x) -<br>x)$, where $D$ is a positive diagonal matrix. The non-uniform dynamics is more<br>complex than the uniform dynamics (with $D$ being the identity matrix), as it<br>allows each component of $x$ to react with different speed to the differences<br>between $q(x)$ and $x$. Our contribution is to show that the non-uniform<br>directed dynamics solves positive linear programs.<br> %K Mathematics, Dynamical Systems, math.DS,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Optimization and Control, math.OC

%0 Report %A Karrenbauer, Andreas %A Kolev, Pavel %A 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 Convergence of the Non-Uniform Physarum Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-0002-F39F-9 %U http://arxiv.org/abs/1901.07231 %D 2019 %X Let $c \in \mathbb{Z}^m_{> 0}$, $A \in \mathbb{Z}^{n\times m}$, and $b \in<br>\mathbb{Z}^n$. We show under fairly general conditions that the non-uniform<br>Physarum dynamics \[ \dot{x}_e = a_e(x,t) \left(|q_e| - x_e\right) \] converges<br>to the optimum solution $x^*$ of the weighted basis pursuit problem minimize<br>$c^T x$ subject to $A f = b$ and $|f| \le x$. Here, $f$ and $x$ are $m$-vectors<br>of real variables, $q$ minimizes the energy $\sum_e (c_e/x_e) q_e^2$ subject to<br>the constraints $A q = b$ and $\mathrm{supp}(q) \subseteq \mathrm{supp}(x)$,<br>and $a_e(x,t) > 0$ is the reactivity of edge $e$ to the difference $|q_e| -<br>x_e$ at time $t$ and in state $x$. Previously convergence was only shown for<br>the uniform case $a_e(x,t) = 1$ for all $e$, $x$, and $t$. We also show<br>convergence for the dynamics \[ \dot{x}_e = x_e \cdot \left( g_e<br>\left(\frac{|q_e|}{x_e}\right) - 1\right),\] where $g_e$ is an increasing<br>differentiable function with $g_e(1) = 1$. Previously convergence was only<br>shown for the special case of the shortest path problem on a graph consisting<br>of two nodes connected by parallel edges.<br> %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Ray Chaudhury, Bhaskar %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Sgouritsa, Alkmini %+ 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 %T A Little Charity Guarantees Almost Envy-Freeness : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4FB8-4 %U http://arxiv.org/abs/1907.04596 %D 2019 %X Fair division of indivisible goods is a very well-studied problem. The goal<br>of this problem is to distribute $m$ goods to $n$ agents in a "fair" manner,<br>where every agent has a valuation for each subset of goods. We assume general<br>valuations.<br> Envy-freeness is the most extensively studied notion of fairness. However,<br>envy-free allocations do not always exist when goods are indivisible. The<br>notion of fairness we consider here is "envy-freeness up to any good" (EFX)<br>where no agent envies another agent after the removal of any single good from<br>the other agent's bundle. It is not known if such an allocation always exists<br>even when $n=3$.<br> We show there is always a partition of the set of goods into $n+1$ subsets<br>$(X_1,\ldots,X_n,P)$ where for $i \in [n]$, $X_i$ is the bundle allocated to<br>agent $i$ and the set $P$ is unallocated (or donated to charity) such that we<br>have$\colon$<br> 1) envy-freeness up to any good,<br> 2) no agent values $P$ higher than her own bundle, and<br> 3) fewer than $n$ goods go to charity, i.e., $|P| < n$ (typically $m \gg n$).<br> Our proof is constructive. When agents have additive valuations and $\lvert P<br>\rvert$ is large (i.e., when $|P|$ is close to $n$), our allocation also has a<br>good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm<br>also shows the existence of an allocation which is $4/7$ groupwise maximin<br>share (GMMS): this is a notion of fairness stronger than MMS. This improves<br>upon the current best bound of $1/2$ known for an approximate GMMS allocation.<br> %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Book %A Sanders, Peter %A Mehlhorn, Kurt %A Dietzfelbinger, Martin %A Dementiev, Roman %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox %G eng %U http://hdl.handle.net/21.11116/0000-0005-3D79-0 %R 10.1007/978-3-030-25209-0 %@ 978-3-030-25208-3 %@ 978-3-030-25209-0 %I Springer %C Cham %D 2019 %P 434 p.

%0 Conference Proceedings %A Chalermsook, Parinya %A Goswami, Mayank %A Kozma, L&#224;sz&#242; %A Mehlhorn, Kurt %A Saranurak, Thatchaphol %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Multi-Finger Binary Search Trees : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AADE-5 %R 10.4230/LIPIcs.ISAAC.2018.55 %U urn:nbn:de:0030-drops-100032 %D 2018 %B 29th International Symposium on Algorithms and Computation %Z date of event: 2018-12-16 - 2018-12-19 %C Jiaoxi, Yilan, Taiwan %B 29th International Symposium on Algorithms and Computation %E Hsu, Wen-Lian; Lee, Der-Tsai; Liao, Chung-Shou %P 1 - 26 %Z sequence number: 55 %I Schloss Dagstuhl %@ 978-3-95977-094-1 %B Leibniz International Proceedings in Informatics %N 123 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2018/10003/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Journal Article %A Croitoru, Cosmina %A Mehlhorn, Kurt %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On Testing Substitutability : %G eng %U http://hdl.handle.net/21.11116/0000-0001-EE14-D %R 10.1016/j.ipl.2018.05.006 %7 2018 %D 2018 %J Information Processing Letters %V 138 %& 19 %P 19 - 21 %I Elsevier %C Amsterdam %@ false

%0 Report %A Croitoru, Cosmina %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On Testing Substitutability : %G eng %U http://hdl.handle.net/21.11116/0000-0002-05FA-F %U http://arxiv.org/abs/1805.07642 %D 2018 %X The papers~\cite{hatfimmokomi11} and~\cite{azizbrilharr13} propose algorithms for testing whether the choice function induced by a (strict) preference list of length $N$ over a universe $U$ is substitutable. The running time of these algorithms is $O(|U|^3\cdot N^3)$, respectively $O(|U|^2\cdot N^3)$. In this note we present an algorithm with running time $O(|U|^2\cdot N^2)$. Note that $N$ may be exponential in the size $|U|$ of the universe. %K Computer Science, Data Structures and Algorithms, cs.DS,econ.EM

%0 Conference Proceedings %A Garg, Jugal %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Approximating the Nash Social Welfare with Budget-Additive Valuations : %G eng %U http://hdl.handle.net/21.11116/0000-0000-37F9-A %R 10.1137/1.9781611975031.150 %D 2018 %B Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2018-01-07 - 2018-01-10 %C New Orleans, LA, USA %B Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms %E Czumaj, Artur %P 2326 - 2340 %I SIAM %@ 978-1-61197-503-1

%0 Journal Article %A Koprowski, Przemys&#322;aw %A Mehlhorn, Kurt %A Ray, Saurabh %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Corrigendum to &#8220;Faster algorithms for computing Hong's bound on absolute positiveness&#8221; [J. Symb. Comput. 45 (2010) 677&#8211;683] : %G eng %U http://hdl.handle.net/21.11116/0000-0001-3C55-D %R 10.1016/j.jsc.2017.05.008 %7 2017 %D 2018 %J Journal of Symbolic Computation %V 87 %& 238 %P 238 - 241 %I Elsevier %C Amsterdam %@ false

%0 Report %A Ray Chaudhury, Bhaskar %A Cheung, Yun Kuen %A Garg, Jugal %A Garg, Naveen %A Hoefer, Martin %A Mehlhorn, Kurt %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On Fair Division of Indivisible Items : %G eng %U http://hdl.handle.net/21.11116/0000-0002-05E7-4 %U http://arxiv.org/abs/1805.06232 %D 2018 %X We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric mean of the utilities of the agents. Each good comes in multiple items or copies, and the utility of an agent diminishes as it receives more items of the same good. The utility of a bundle of items for an agent is the sum of the utilities of the items in the bundle. Each agent has a utility cap beyond which he does not value additional items. We give a polynomial time approximation algorithm that maximizes Nash social welfare up to a factor of $e^{1/e} \approx 1.445$. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Cheung, Yun Kuen %A Garg, Jugal %A Garg, Naveen %A Hoefer, Martin %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On Fair Division for Indivisible Items : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AAE1-0 %R 10.4230/LIPIcs.FSTTCS.2018.25 %U urn:nbn:de:0030-drops-99242 %D 2018 %B 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science %Z date of event: 2018-12-11 - 2018-12-13 %C Ahmedabad, India %B 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science %E Ganguly, Sumit; Pandya, Paritosh %P 1 - 17 %Z sequence number: 25 %I Schloss Dagstuhl %@ 978-3-95977-093-4 %B Leibniz International Proceedings in Informatics %N 122 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2018/9924/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Report %A Ray Chaudhury, Bhaskar %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Combinatorial Algorithms for General Linear Arrow-Debreu Markets : %G eng %U http://hdl.handle.net/21.11116/0000-0002-57B5-0 %U http://arxiv.org/abs/1810.01237 %D 2018 %8 02.10.2018 %X We present a combinatorial algorithm for determining the market clearing<br>prices of a general linear Arrow-Debreu market, where every agent can own<br>multiple goods. The existing combinatorial algorithms for linear Arrow-Debreu<br>markets consider the case where each agent can own all of one good only. We<br>present an $\tilde{\mathcal{O}}((n+m)^7 \log^3(UW))$ algorithm where $n$, $m$,<br>$U$ and $W$ refer to the number of agents, the number of goods, the maximal<br>integral utility and the maximum quantity of any good in the market<br>respectively. The algorithm refines the iterative algorithm of Duan, Garg and<br>Mehlhorn using several new ideas. We also identify the hard instances for<br>existing combinatorial algorithms for linear Arrow-Debreu markets. In<br>particular we find instances where the ratio of the maximum to the minimum<br>equilibrium price of a good is $U^{\Omega(n)}$ and the number of iterations<br>required by the existing iterative combinatorial algorithms of Duan, and<br>Mehlhorn and Duan, Garg, and Mehlhorn are high. Our instances also separate the<br>two algorithms.<br> %K Computer Science, Computer Science and Game Theory, cs.GT,

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Combinatorial Algorithms for General Linear Arrow-Debreu Markets : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AADC-7 %R 10.4230/LIPIcs.FSTTCS.2018.26 %U urn:nbn:de:0030-drops-99255 %D 2018 %B 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science %Z date of event: 2018-12-11 - 2018-12-13 %C Ahmedabad, India %B 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science %E Ganguly, Sumit; Pandya, Paritosh %P 1 - 16 %Z sequence number: 26 %I Schloss Dagstuhl %@ 978-3-95977-093-4 %B Leibniz International Proceedings in Informatics %N 122 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2018/9925/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Report %A Becker, Ruben %A Bonifaci, Vincenzo %A Karrenbauer, Andreas %A Kolev, Pavel %A 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Two Results on Slime Mold Computations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-FBA8-F %U http://arxiv.org/abs/1707.06631 %D 2017 %X In this paper, we present two results on slime mold computations. The first one treats a biologically-grounded model, originally proposed by biologists analyzing the behavior of the slime mold Physarum polycephalum. This primitive organism was empirically shown by Nakagaki et al. to solve shortest path problems in wet-lab experiments (Nature'00). We show that the proposed simple mathematical model actually generalizes to a much wider class of problems, namely undirected linear programs with a non-negative cost vector. For our second result, we consider the discretization of a biologically-inspired model. This model is a directed variant of the biologically-grounded one and was never claimed to describe the behavior of a biological system. Straszak and Vishnoi showed that it can $\epsilon$-approximately solve flow problems (SODA'16) and even general linear programs with positive cost vector (ITCS'16) within a finite number of steps. We give a refined convergence analysis that improves the dependence on $\epsilon$ from polynomial to logarithmic and simultaneously allows to choose a step size that is independent of $\epsilon$. Furthermore, we show that the dynamics can be initialized with a more general set of (infeasible) starting points. %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Dynamical Systems, math.DS,Mathematics, Optimization and Control, math.OC, Physics, Biological Physics, physics.bio-ph

%0 Conference Proceedings %A Bei, Xiaohui %A Garg, Jugal %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Earning Limits in Fisher Markets with Spending-Constraint Utilities : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-E7DB-7 %R 10.1007/978-3-319-66700-3_6 %D 2017 %B 10th International Symposium on Algorithmic Game Theory %Z date of event: 2017-09-12 - 2017-09-14 %C L'Aquila, Italy %B Algorithmic Game Theory %P 67 - 79 %I Springer %@ 978-3-319-66699-0 %B Lecture Notes in Computer Science %N 10504

%0 Journal Article %A Dirnberger, Michael %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Characterizing Networks Formed by P. Polycephalum : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-56FA-2 %R 10.1088/1361-6463/aa6e7b %7 2017 %D 2017 %J Journal of Physics D: Applied Physics %O J. Phys. D: Appl. Phys. %V 50 %N 22 %Z sequence number: 224002 %I IOP Publishing %C Bristol %@ false

%0 Journal Article %A Dirnberger, Michael %A Mehlhorn, Kurt %A Mehlhorn, Tim %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Introducing the Slime Mold Graph Repository : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-8464-B %R 10.1088/1361-6463/aa7326 %7 2017 %D 2017 %J Journal of Physics D: Applied Physics %O J. Phys. D: Appl. Phys. %V 50 %N 26 %Z sequence number: 264001 %I IOP Publishing %C Bristol %@ false

%0 Report %A Garg, Jugal %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Approximating the Nash Social Welfare with Budget-Additive Valuations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-E7D6-2 %U http://arxiv.org/abs/1707.04428 %D 2017 %X We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every $\varepsilon > 0$, our algorithm obtains a $(2.404 + \varepsilon)$-approximation in time polynomial in the input size and $1/\varepsilon$. Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [Cole et al, EC 2017]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computer Science and Game Theory, cs.GT

%0 Journal Article %A Mehlhorn, Kurt %A Neumann, Adrian %A Schmidt, Jens M. %+ 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 Certifying 3-Edge-Connectivity : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-6971-B %R 10.1007/s00453-015-0075-x %7 2015-09-22 %D 2017 %J Algorithmica %V 77 %N 2 %& 309 %P 309 - 335 %I Springer %C New York, NY, USA %@ false

%0 Report %A Mehlhorn, Kurt %A N&#228;her, Stefan %A Sanders, Peter %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Engineering DFS-Based Graph Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-4DAE-7 %U http://arxiv.org/abs/1703.10023 %D 2017

%0 Report %A Becker, Ruben %A Karrenbauer, Andreas %A 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 An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5714-E %U http://arxiv.org/abs/1612.04689 %D 2016 %X We present an interior point method for the min-cost flow problem that uses arc contractions and deletions to steer clear from the boundary of the polytope when path-following methods come too close. We obtain a randomized algorithm running in expected $\tilde O( m^{3/2} )$ time that only visits integer lattice points in the vicinity of the central path of the polytope. This enables us to use integer arithmetic like classical combinatorial algorithms typically do. We provide explicit bounds on the size of the numbers that appear during all computations. By presenting an integer arithmetic interior point algorithm we avoid the tediousness of floating point error analysis and achieve a method that is guaranteed to be free of any numerical issues. We thereby eliminate one of the drawbacks of numerical methods in contrast to combinatorial min-cost flow algorithms that still yield the most efficient implementations in practice, despite their inferior worst-case time complexity. %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Numerical Analysis, math.NA,Mathematics, Optimization and Control, math.OC

%0 Conference Proceedings %A Bei, Xiaohui %A Garg, Jugal %A Hoefer, Martin %A 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Computing Equilibria in Markets with Budget-Additive Utilities : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-479B-5 %R 10.4230/LIPIcs.ESA.2016.8 %U urn:nbn:de:0030-drops-63504 %D 2016 %B 24th Annual European Symposium on Algorithms %Z date of event: 2016-08-22 - 2016-08-26 %C Aarhus, Denmark %B 24th Annual European Symposium on Algorithms %E Sankowski, Piotr; Zaroliagis, Christos %P 1 - 14 %Z sequence number: 8 %I Schloss Dagstuhl %@ 978-3-95977-015-6 %B Leibniz International Proceedings in Informatics %N 57 %U http://drops.dagstuhl.de/opus/volltexte/2016/6350/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Report %A Bei, Xiaohui %A Garg, Jugal %A Hoefer, Martin %A 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Computing Equilibria in Markets with Budget-Additive Utilities : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002A-FCC0-C %U http://arxiv.org/abs/1603.07210 %D 2016 %X We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement these positive results with a number of hardness results for related computational questions. We prove that it is NP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good. %K Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Chalermsook, Parinya %A Goswami, Mayank %A Kozma, L&#225;szl&#243; %A Mehlhorn, Kurt %A Saranurak, Thatchaphol %+ 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 The Landscape of Bounds for Binary Search Trees : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002A-FCC9-9 %U http://arxiv.org/abs/1603.04892 %D 2016 %X Binary search trees (BSTs) with rotations can adapt to various kinds of structure in search sequences, achieving amortized access times substantially better than the Theta(log n) worst-case guarantee. Classical examples of structural properties include static optimality, sequential access, working set, key-independent optimality, and dynamic finger, all of which are now known to be achieved by the two famous online BST algorithms (Splay and Greedy). (...) In this paper, we introduce novel properties that explain the efficiency of sequences not captured by any of the previously known properties, and which provide new barriers to the dynamic optimality conjecture. We also establish connections between various properties, old and new. For instance, we show the following. (i) A tight bound of O(n log d) on the cost of Greedy for d-decomposable sequences. The result builds on the recent lazy finger result of Iacono and Langerman (SODA 2016). On the other hand, we show that lazy finger alone cannot explain the efficiency of pattern avoiding sequences even in some of the simplest cases. (ii) A hierarchy of bounds using multiple lazy fingers, addressing a recent question of Iacono and Langerman. (iii) The optimality of the Move-to-root heuristic in the key-independent setting introduced by Iacono (Algorithmica 2005). (iv) A new tool that allows combining any finite number of sound structural properties. As an application, we show an upper bound on the cost of a class of sequences that all known properties fail to capture. (v) The equivalence between two families of BST properties. The observation on which this connection is based was known before - we make it explicit, and apply it to classical BST properties. (...) %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Croitoru, Cosmina %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Opposition Frameworks : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-57A8-4 %R 10.1007/978-3-319-48758-8_13 %D 2016 %B 15th European Conference on Logics in Artificial Intelligence %Z date of event: 2016-11-09 - 2016-11-11 %C Larnaca, Cyprus %B Logics in Artificial Intelligence %E Michael, Loizos; Kakas, Antonios %P 190 - 206 %I Springer %@ 978-3-319-48757-1 %B Lecture Notes in Artificial Intelligence %N 10021

%0 Journal Article %A Darwish, Omar %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improved Balanced Flow Computation Using Parametric Flow : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002A-FC7B-A %R 10.1016/j.ipl.2016.04.008 %7 2016-04-22 %D 2016 %J Information Processing Letters %V 116 %N 9 %& 560 %P 560 - 563 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Duan, Ran %A Garg, Jugal %A 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 An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-81DD-9 %R 10.1137/1.9781611974331.ch7 %D 2016 %B Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2016-01-10 - 2016-01-12 %C Arlington, VA, USA %X We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with $n$ agents and integral utilities bounded by $U$, the algorithm runs in $O(n^7 \log^3 (nU))$ time. This improves upon the previously best algorithm of Ye by a factor of $\tOmega(n)$. The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of $\tOmega(n^3)$. The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy. %B Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms %E Krauthgamer, Robert %P 90 - 106 %I SIAM %@ 978-1-61197-433-1

%0 Journal Article %A Elbassioni, Khaled %A Mehlhorn, Kurt %A Ramezani, Fahimeh %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-0B1C-9 %R 10.1007/s00224-016-9704-2 %7 2016 %D 2016 %J Theory of Computing Systems %V 59 %N 4 %& 641 %P 641 - 663 %I Springer %C New York, NY %@ false

%0 Journal Article %A Huang, Chien-Chung %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Michail, Dimitrios %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Fair Matchings and Related Problems : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002A-115F-4 %R 10.1007/s00453-015-9994-9 %7 2016 %D 2016 %J Algorithmica %V 74 %N 3 %& 1184 %P 1184 - 1203 %I Springer %C New York, NY %@ false

%0 Conference Proceedings %A Kolev, Pavel %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Note On Spectral Clustering : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-4797-D %U urn:nbn:de:0030-drops-63994 %R 10.4230/LIPIcs.ESA.2016.57 %D 2016 %B 24th Annual European Symposium on Algorithms %Z date of event: 2016-08-22 - 2016-08-26 %C Aarhus, Denmark %B 24th Annual European Symposium on Algorithms %E Sankowski, Piotr; Zaroliagis, Christos %P 1 - 14 %Z sequence number: 57 %I Schloss Dagstuhl %@ 978-3-95977-015-6 %B Leibniz International Proceedings in Informatics %N 57 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2016/6399/http://drops.dagstuhl.de/doku/urheberrecht1.html

%0 Journal Article %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Algorithms and Programs: Erasmus Lecture 2014 : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002A-07A2-A %R 10.1017/S1062798715000381 %7 2016 %D 2016 %J European Review %V 24 %N 1 %& 4 %P 4 - 16 %I Cambridge University Press %C Cambridge %@ false

%0 Journal Article %A Mehlhorn, Kurt %A Saxena, Sanjeev %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-7CA0-D %R 10.1016/j.cosrev.2016.07.001 %7 2016 %D 2016 %J Computer Science Review %V 22 %& 1 %P 1 - 11 %I Elsevier %C Amsterdam

%0 Journal Article %A Sagraloff, Michael %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Computing Real Roots of Real Polynomials : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0025-0B82-A %R 10.1016/j.jsc.2015.03.004 %7 2015 %D 2016 %J Journal of Symbolic Computation %V 73 %& 46 %P 46 - 86 %I Academic Press %C London %@ false

%0 Conference Proceedings %A Chalermsook, Parinya %A Goswami, Mayank %A Kozma, L&#225;szl&#243; %A Mehlhorn, Kurt %A Saranurak, Thatchaphol %+ 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 Pattern-avoiding Access in Binary Search Trees : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002A-078B-F %R 10.1109/FOCS.2015.32 %D 2015 %B IEEE 56th Annual Symposium on Foundations of Computer Science %Z date of event: 2015-10-18 - 2015-10-20 %C Berkeley, CA, USA %B FOCS 2015 %P 410 - 423 %I IEEE

%0 Report %A Chalermsook, Parinya %A Goswami, Mayank %A Kozma, Laszlo %A Mehlhorn, Kurt %A Saranurak, Thatchaphol %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Greedy Is an Almost Optimal Deque : %U http://hdl.handle.net/11858/00-001M-0000-0027-D400-5 %U http://arxiv.org/abs/1506.08319 %D 2015 %X In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Patrascu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online Greedy BST algorithm introduced by DHIKP. Greedy BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal. With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of Greedy BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that Greedy BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004). As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is Omega(log |U| + n) on "most" of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Omega(n log n) with high probability. Besides the splay tree noted before, Greedy BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing Greedy BST. Our work is intended as a step towards a full understanding of Greedy BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Chalermsook, Parinya %A Goswami, Mayank %A Kozma, L&#225;sl&#243; %A Mehlhorn, Kurt %A Saranurak, Thatchaphol %+ 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 Greedy Is an Almost Optimal Deque : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-8F41-6 %R 10.1007/978-3-319-21840-3_13 %D 2015 %B 14th International Symposium on Algorithms and Data Structure %Z date of event: 2015-08-05 - 2015-08-07 %C Victoria, Canada %B Algorithms and Data Structures %E Dehne, Frank; Sack, J&#246;rg-R&#252;diger; Stege, Ulrike %P 152 - 165 %I Springer %@ 978-3-319-21839-7 %B Lecture Notes in Computer Science %N 9214

%0 Conference Proceedings %A Chalermsook, Parinya %A Goswami, Mayank %A Kozma, Laszlo %A Mehlhorn, Kurt %A Saranurak, Thatchaphol %+ 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 Self-Adjusting Binary Search Trees: What Makes Them Tick? : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-667A-C %R 10.1007/978-3-662-48350-3_26 %D 2015 %B 23rd Annual European Symposium on Algorithms %Z date of event: 2015-09-14 - 2015-09-16 %C Patras, Greece %B Algorithms -- ESA 2015 %E Bansal, Nikhil; Finocchi, Irene %P 300 - 312 %I Springer %@ 978-3-662-4834 %B Lecture Notes in Computer Science %N 9294

%0 Report %A Chalermsook, Parinya %A Goswami, Mayank %A Kozma, L&#225;szl&#243; %A Mehlhorn, Kurt %A Saranurak, Thatchaphol %+ 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 Pattern-avoiding Access in Binary Search Trees : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-8F4C-0 %U http://arxiv.org/abs/1507.06953 %D 2015 %X The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e. one that is constant factor competitive with any BST on any input access sequence. The two main candidates for dynamic optimality in the literature are splay trees [Sleator and Tarjan, 1985], and Greedy [Lucas, 1988; Munro, 2000; Demaine et al. 2009] [..] Dynamic optimality is trivial for almost all sequences: the optimum access cost of most length-n sequences is Theta(n log n), achievable by any balanced BST. Thus, the obvious missing step towards the conjecture is an understanding of the "easy" access sequences. [..] The difficulty of proving dynamic optimality is witnessed by highly restricted special cases that remain unresolved; one prominent example is the traversal conjecture [Sleator and Tarjan, 1985], which states that preorder sequences (whose optimum is linear) are linear-time accessed by splay trees; no online BST is known to satisfy this conjecture. In this paper, we prove two different relaxations of the traversal conjecture for Greedy: (i) Greedy is almost linear for preorder traversal, (ii) if a linear-time preprocessing is allowed, Greedy is in fact linear. These statements are corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. [..] To our knowledge, these are the first upper bounds for Greedy that are not known to hold for any other online BST. To obtain these results we identify an input-revealing property of Greedy. Informally, this means that the execution log partially reveals the structure of the access sequence. This property facilitates the use of rich technical tools from forbidden submatrix theory. [Abridged] %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Combinatorics, math.CO

%0 Report %A Chalermsook, Parinya %A Goswami, Mayank %A Kozma, Laszlo %A Mehlhorn, Kurt %A Saranurak, Thatchaphol %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Self-Adjusting Binary Search Trees: What Makes Them Tick? : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0027-D3FB-E %U http://arxiv.org/abs/1503.03105 %D 2015 %X Splay trees (Sleator and Tarjan) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs) satisfy the access lemma? After each access, self-adjusting BSTs replace the search path by a tree on the same set of nodes (the after-tree). We identify two simple combinatorial properties of the search path and the after-tree that imply the access lemma. Our main result (i) implies the access lemma for all minimally self-adjusting BST algorithms for which it was known to hold: splay trees and their generalization to the class of local algorithms (Subramanian, Georgakopoulos and Mc-Clurkin), as well as Greedy BST, introduced by Demaine et al. and shown to satisfy the access lemma by Fox, (ii) implies that BST algorithms based on "strict" depth-halving satisfy the access lemma, addressing an open question that was raised several times since 1985, and (iii) yields an extremely short proof for the O(log n log log n) amortized access cost for the path-balance heuristic (proposed by Sleator), matching the best known bound (Balasubramanian and Raman) to a lower-order factor. One of our combinatorial properties is locality. We show that any BST-algorithm that satisfies the access lemma via the sum-of-log (SOL) potential is necessarily local. The other property states that the sum of the number of leaves of the after-tree plus the number of side alternations in the search path must be at least a constant fraction of the length of the search path. We show that a weak form of this property is necessary for sequential access to be linear. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Report %A Darwish, Omar %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improved Balanced Flow Computation Using Parametric Flow : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0029-4A62-F %U http://arxiv.org/abs/1512.05974 %D 2015 %X We present a new algorithm for computing balanced flows in equality networks arising in market equilibrium computations. The current best time bound for computing balanced flows in such networks requires $O(n)$ maxflow computations, where $n$ is the number of nodes in the network [Devanur et al. 2008]. Our algorithm requires only a single parametric flow computation. The best algorithm for computing parametric flows [Gallo et al. 1989] is only by a logarithmic factor slower than the best algorithms for computing maxflows. Hence, the running time of the algorithms in [Devanur et al. 2008] and [Duan and Mehlhorn 2015] for computing market equilibria in linear Fisher and Arrow-Debreu markets improve by almost a factor of $n$. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computer Science and Game Theory, cs.GT

%0 Journal Article %A Duan, Ran %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0027-AC93-6 %R 10.1016/j.ic.2014.12.009 %7 2015 %D 2015 %J Information and Computation %V 243 %& 112 %P 112 - 132 %I Academic Press %C San Diego %@ false

%0 Report %A Duan, Ran %A Garg, Jugal %A 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 An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-88EC-3 %U http://arxiv.org/abs/1510.02694 %D 2015 %8 16.10.2015 %X We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with $n$ agents and integral utilities bounded by $U$, the algorithm runs in $O(n^7 \log^3 (nU))$ time. This improves upon the previously best algorithm of Ye by a factor of $\tOmega(n)$. The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of $\tOmega(n^3)$. The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computer Science and Game Theory, cs.GT

%0 Conference Proceedings %A Elbassioni, Khaled %A Mehlhorn, Kurt %A Ramezani, Fahimeh %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-8F3C-3 %R 10.1007/978-3-662-48433-3_8 %D 2015 %B 8th International Symposium on Algorithmic Game Theory %Z date of event: 2015-09-28 - 2015-09-30 %C Saarbr&#252;cken, Germany %B Algorithmic Game Theory %E Hoefer, Martin %P 98 - 109 %I Springer %@ 978-3-662-48432-6 %B Lecture Notes in Computer Science %N 9347

%0 Journal Article %A Elbassioni, Khaled %A Makino, Kazuhisa %A Mehlhorn, Kurt %A Ramezani, Fahimeh %+ 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 %T On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-669E-B %R 10.1007/s00453-014-9902-8 %7 2015 %D 2015 %J Algorithmica %V 73 %N 2 %& 441 %P 441 - 459 %I Springer %C New York, NY %@ false

%0 Report %A Kolev, Pavel %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Note On Spectral Clustering : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-8F4F-A %U http://arxiv.org/abs/1509.09188 %D 2015 %X Let $G=(V,E)$ be an undirected graph, $\lambda_k$ the $k$th smallest eigenvalue of the normalized Laplacian matrix of $G$, and $\rho(k)$ the smallest value of the maximal conductance over all $k$-way partitions $S_1,\dots,S_k$ of $V$. Peng et al. [PSZ15] gave the first rigorous analysis of $k$-clustering algorithms that use spectral embedding and $k$-means clustering algorithms to partition the vertices of a graph $G$ into $k$ disjoint subsets. Their analysis builds upon a gap parameter $\Upsilon=\rho(k)/\lambda_{k+1}$ that was introduced by Oveis Gharan and Trevisan [GT14]. In their analysis Peng et al. [PSZ15] assume a gap assumption $\Upsilon\geq\Omega(\mathrm{APR}\cdot k^3)$, where $\mathrm{APR}>1$ is the approximation ratio of a $k$-means clustering algorithm. We exhibit an error in one of their Lemmas and provide a correction. With the correction the proof by Peng et al. [PSZ15] requires a stronger gap assumption $\Upsilon\geq\Omega(\mathrm{APR}\cdot k^4)$. Our main contribution is to improve the analysis in [PSZ15] by an $O(k)$ factor. We demonstrate that a gap assumption $\Psi\geq \Omega(\mathrm{APR}\cdot k^3)$ suffices, where $\Psi=\rho_{avr}(k)/\lambda_{k+1}$ and $\rho_{avr}(k)$ is the value of the average conductance of a partition $S_1,\dots,S_k$ of $V$ that yields $\rho(k)$. %K Computer Science, Discrete Mathematics, cs.DM

%0 Report %A Mehlhorn, Kurt %A Saxena, Sanjeev %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-F70B-6 %U http://arxiv.org/abs/1510.03339 %D 2015 %X Linear programming is now included in algorithm undergraduate and postgraduate courses for computer science majors. We show that it is possible to teach interior-point methods directly to students with just minimal knowledge of linear algebra. %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Optimization and Control, math.OC

%0 Journal Article %A Mehlhorn, Kurt %A Sagraloff, Michael %A Wang, Pengming %+ 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 From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-36CF-A %R 10.1016/j.jsc.2014.02.001 %7 2014-02-21 %D 2015 %J Journal of Symbolic Computation %V 66 %& 34 %P 34 - 69 %I Academic Press %C London %@ false

%0 Book Section %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On the Implementation of Combinatorial Algorithms for the Linear Exchange Market : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0028-8F36-F %D 2015 %B Algorithms, Probability, Networks, and Games %E Zaroliagis, Christos; Pantziou, Grammati; Kontogianni, Spyros; Spirakis, Paul G. %P 87 - 94 %I Springer %C Berlin %@ 978-3-319-24023-7 %S Lecture Notes in Computer Science %N 9295

%0 Book Section %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T From Theory to Library of Efficient Data Types and Algorithms (LEDA) and Algorithm Engineering : Chapter 5 %G eng %U http://hdl.handle.net/11858/00-001M-0000-002A-0799-F %R 10.1142/9781783266449_0005 %D 2015 %B The Human Face of Computing %E Calude, Christian S. %P 59 - 71 %I Imperial College Press %C London %@ 978-1-78326-643-2 978-1-78326-645-6 %S Advances in Computer Science and Engineering %N 9

%0 Journal Article %A Alkassar, Eyad %A B&#246;hme, Sascha %A Mehlhorn, Kurt %A Rizkallah, Christine %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Framework for the Verification of Certifying Computations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-3DF3-7 %R 10.1007/s10817-013-9289-2 %7 2013-06-29 %D 2014 %K Computer Science, Logic in Computer Science, cs.LO,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Formal Languages and Automata Theory, cs.FL %J Journal of Automated Reasoning %V 52 %N 3 %& 241 %P 241 - 273 %I Springer %C Dordrecht, Holland %@ false

%0 Conference Proceedings %A Bhattacharya, Sayan %A Chalermsook, Parinya %A Mehlhorn, Kurt %A Neumann, Adrian %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T New Approximability Results for the Robust k-Median Problem : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-447B-6 %R 10.1007/978-3-319-08404-6_5 %D 2014 %B 14th Scandinavian Symposium and Workshops on Algorithm Theory %Z date of event: 2014-07-02 - 2014-07-04 %C Copenhagen, Denmark %B Algorithm Theory -- SWAT 2014 %E G&#248;rtz, Inge Li; Ravi, R. %P 50 - 61 %I Springer %@ 978-3-319-08403-9 %B Lecture Notes in Computer Science %N 8503

%0 Journal Article %A Christodoulou, George %A Mehlhorn, Kurt %A Pyrga, Evangelia %+ 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 Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E27-D %R 10.1007/s00453-013-9753-8 %7 2013-02-15 %D 2014 %J Algorithmica %V 69 %N 3 %& 619 %P 619 - 640 %I Springer-Verlag %C New York, NY %@ false

%0 Book %A Dietzfelbinger, Martin %A Mehlhorn, Kurt %A Sanders, Peter %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Algorithmen und Datenstrukturen : die Grundwerkzeuge : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E17-2 %@ 978-3-642-05472-3 %R 10.1007/978-3-642-05472-3_1 %I Springer Vieweg %C Berlin %D 2014 %P XII, 380 p. %B eXamen press

%0 Report %A Elbassioni, Khaled %A Makino, Kazuhisa %A Mehlhorn, Kurt %A Ramezani, Fahimeh %+ 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 %T On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E4C-C %U http://arxiv.org/abs/1301.5290 %D 2014 %X Given two bounded convex sets $X\subseteq\RR^m$ and $Y\subseteq\RR^n,$ specified by membership oracles, and a continuous convex-concave function $F:X\times Y\to\RR$, we consider the problem of computing an $\eps$-approximate saddle point, that is, a pair $(x^*,y^*)\in X\times Y$ such that $\sup_{y\in Y} F(x^*,y)\le \inf_{x\in X}F(x,y^*)+\eps.$ Grigoriadis and Khachiyan (1995) gave a simple randomized variant of fictitious play for computing an $\eps$-approximate saddle point for matrix games, that is, when $F$ is bilinear and the sets $X$ and $Y$ are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant "width", an $\eps$-approximate saddle point can be computed using $O^*(\frac{(n+m)}{\eps^2}\ln R)$ random samples from log-concave distributions over the convex sets $X$ and $Y$. It is assumed that $X$ and $Y$ have inscribed balls of radius $1/R$ and circumscribing balls of radius $R$. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when $\eps \in (0,1)$ is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets. %K Computer Science, Computer Science and Game Theory, cs.GT,Mathematics, Optimization and Control, math.OC

%0 Report %A Elbassioni, Khaled %A Mehlhorn, Kurt %A Ramezani, Fahimeh %+ 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 Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-490A-B %U http://arxiv.org/abs/1408.1577 %D 2014 %8 07.08.2014 %X R. Lavy and C. Swamy (FOCS 2005, J. ACM 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees. %K Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Jurkiewicz, Tomasz %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On a Model of Virtual Address Translation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-E593-C %R 10.1145/2656337 %7 2014 %D 2014 %J Journal of Experimental Algorithmics %O JEA J. Exp. Algorithmics %V 19 %& 1 %P 1 - 28 %Z sequence number: 1.9 %I ACM %C New York, NY %@ false

%0 Report %A Jurkiewicz, Tomasz %A Mehlhorn, Kurt %A Nicholson, Patrick %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Cache-Oblivious VAT-Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-36C2-4 %U http://arxiv.org/abs/1404.3577 %D 2014 %8 14.01.2014 %X The VAT-model (virtual address translation model) extends the EM-model (external memory model) and takes the cost of address translation in virtual memories into account. In this model, the cost of a single memory access may be logarithmic in the largest address used. We show that the VAT-cost of cache-oblivious algorithms is only by a constant factor larger than their EM-cost; this requires a somewhat more stringent tall cache assumption as for the EM-model. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %E Megiddo, Nimrod %E Mehlhorn, Kurt %E Savani, Rahul %E Vazirani, Vijay V. %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Equilibrium Computation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E35-D %R 10.4230/DagRep.4.8.73 %U urn:nbn:de:0030-drops-47990 %I Schloss Dagstuhl %D 2014 %8 09.12.2014 %B Dagstuhl Seminar 14342 &#8220;Equilibrium Computation" %Z date of event: 2014-08-17 - 2014-08-22 %D 2014 %C Wadern, Germany %P 16 p. %S Dagstuhl Reports %V 4 %P 73 - 88 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2014/4799/

%0 Conference Proceedings %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Algorithms for Equilibrium Prices in Linear Market Models : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-4ACF-9 %R 10.1007/978-3-319-04657-0_1 %D 2014 %B 8th International Workshop on Algorithms and Computation %Z date of event: 2014-02-13 - 2014-02-15 %C Chennai, India %B Algorithms and Computation %E Pal, Sudebkumar Prasant; Sadakane, Kunihiko %P 1 - 4 %I Springer %@ 978-3-319-04656-3 %B Lecture Notes in Computer Science %N 8344

%0 Conference Proceedings %A Noschinski, Lars %A Rizkallah, Christine %A Mehlhorn, Kurt %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Verification of Certifying Computations through AutoCorres and Simpl : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5B03-4 %R 10.1007/978-3-319-06200-6_4 %D 2014 %B Sixth NASA Formal Methods Symposium %Z date of event: 2014-04-29 - 2014-05-01 %C Houston, TX, USA %B NASA Formal Methods %E Badger, Julia M.; Rozier, Kristin Yvonne %P 46 - 61 %I Springer %@ 978-3-319-06199-3 %B Lecture Notes in Computer Science %N 8430

%0 Book Section %A Afshani, Peyman %A Agrawal, Manindra %A Doerr, Benjamin %A Doerr, Carola %A Larsen, Kasper Green %A Mehlhorn, Kurt %+ External Organizations 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 The Query Complexity of Finding a Hidden Permutation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0015-3AC3-A %F OTHER: Local_ID: 20EA14F7E5BB5FE7C1257C53007A351B-Afshani2013 %R 10.1007/978-3-642-40273-9_1 %D 2013 %B Space-Efficient Data Structures, Streams, and Algorithms %E Brodnik, Andrej; L&#243;pez-Ortiz, Alejandro; Raman, Venkatesh; Viola, Alfredo %P 1 - 11 %I Springer %C Berlin %@ 978-3-642-40272-2 %S Lecture Notes in Computer Science %N 8066

%0 Report %A Alkassar, Eyad %A B&#246;hme, Sascha %A Mehlhorn, Kurt %A Rizkallah, Christine %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Framework for the Verification of Certifying Computations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-3DF0-D %U http://arxiv.org/abs/1301.7462 %D 2013 %8 30.01.2013 %X Formal verification of complex algorithms is challenging. Verifying their implementations goes beyond the state of the art of current automatic verification tools and usually involves intricate mathematical theorems. Certifying algorithms compute in addition to each output a witness certifying that the output is correct. A checker for such a witness is usually much simpler than the original algorithm - yet it is all the user has to trust. The verification of checkers is feasible with current tools and leads to computations that can be completely trusted. We describe a framework to seamlessly verify certifying computations. We use the automatic verifier VCC for establishing the correctness of the checker and the interactive theorem prover Isabelle/HOL for high-level mathematical properties of algorithms. We demonstrate the effectiveness of our approach by presenting the verification of typical examples of the industrial-level and widespread algorithmic library LEDA. %K Computer Science, Logic in Computer Science, cs.LO,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Formal Languages and Automata Theory, cs.FL

%0 Conference Proceedings %A Becchetti, Luca %A Bonifaci, Vincenzo %A Dirnberger, Michael %A Karrenbauer, Andreas %A Mehlhorn, Kurt %+ 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 Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-43EA-3 %R 10.1007/978-3-642-39212-2_42 %D 2013 %B 40th International Colloquium on Automata, Languages and Programming %Z date of event: 2013-07-08 - 2013-07-12 %C Riga, Latvia %B Automata, Languages, and Programming %E Fomin, Fedor V.; Freivalds, R&#363;si&#326;&#353;; Kwiatkowska, Marta; Peleg, David %P 472 - 483 %I Springer %@ 978-3-642-39211-5 %B Lecture Notes in Computer Science %N 7966

%0 Report %A Bhattacharya, Sayan %A Chalermsook, Parinya %A Mehlhorn, Kurt %A Neumann, Adrian %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T New Approximability Results for the Robust k-Median Problem : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E4F-6 %U http://arxiv.org/abs/1309.4602 %D 2013 %X We consider a robust variant of the classical $k$-median problem, introduced by Anthony et al. \cite{AnthonyGGN10}. In the \emph{Robust $k$-Median problem}, we are given an $n$-vertex metric space $(V,d)$ and $m$ client sets $\set{S_i \subseteq V}_{i=1}^m$. The objective is to open a set $F \subseteq V$ of $k$ facilities such that the worst case connection cost over all client sets is minimized; in other words, minimize $\max_{i} \sum_{v \in S_i} d(F,v)$. Anthony et al.\ showed an $O(\log m)$ approximation algorithm for any metric and APX-hardness even in the case of uniform metric. In this paper, we show that their algorithm is nearly tight by providing $\Omega(\log m/ \log \log m)$ approximation hardness, unless ${\sf NP} \subseteq \bigcap_{\delta >0} {\sf DTIME}(2^{n^{\delta}})$. This hardness result holds even for uniform and line metrics. To our knowledge, this is one of the rare cases in which a problem on a line metric is hard to approximate to within logarithmic factor. We complement the hardness result by an experimental evaluation of different heuristics that shows that very simple heuristics achieve good approximations for realistic classes of instances. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %E Cheong, Otfried %E Mehlhorn, Kurt %E Teillaud, Monique %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Computational Geometry : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E6A-6 %R 10.4230/DagRep.3.3.1 %U urn:nbn:de:0030-drops-40210 %I Schloss Dagstuhl %D 2013 %8 04.07.2013 %B Dagstuhl Seminar 13101 "Computational Geometry" %Z date of event: 2013-03-03 - 2013-03-08 %D 2013 %C Wadern, Germany %S Dagstuhl Reports %V 3 %P 1 - 23 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2013/4021/

%0 Report %A Christodoulou, George %A Mehlhorn, Kurt %A Pyrga, Evangelia %+ 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 Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-A61F-A %U http://arxiv.org/abs/1202.2877 %D 2013 %8 08.01.2013 %X We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou's network. We improve upon the value 4/3 by means of Coordination Mechanisms. We increase the latency functions of the edges in the network, i.e., if $\ell_e(x)$ is the latency function of an edge $e$, we replace it by $\hat{\ell}_e(x)$ with $\ell_e(x) \le \hat{\ell}_e(x)$ for all $x$. Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if $\CM(r)$ denotes the cost of the worst Nash flow in the modified network for rate $r$ and $\Copt(r)$ denotes the cost of the optimal flow in the original network for the same rate then [\ePoA = \max_{r \ge 0} \frac{\CM(r)}{\Copt(r)}.] We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4 = 1.25. Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192. %K Computer Science, Computer Science and Game Theory, cs.GT

%0 Report %A Duan, Ran %A Mehlhorn, Kurt %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-F74C-E %U http://arxiv.org/abs/1212.0979 %F OTHER: Local-ID: D07870B186956D01C1257AE8000EA12F-DK2012 %D 2013 %8 13.09.2013 %X We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities. %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Duan, Ran %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E4A-0 %R 10.1007/978-3-642-39206-1_36 %D 2013 %B 40th International Colloquium on Automata, Languages and Programming, %Z date of event: 2014-07-08 - 2014-07-12 %C Riga, Latvia %B Automata, Languages, and Programming %E Fomin, Fedor V.; Freivalds, R&#363;si&#326;&#353;; Kwiatkowska , Marta; Peleg, David %P 425 - 436 %I Springer %@ 978-3-642-39205-4 %B Lecture Notes in Computer Science %N 7965

%0 Conference Proceedings %A Elbassioni, Khaled %A Makino, Kazuhisa %A Mehlhorn, Kurt %A Ramezani, Fahimeh %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0015-7905-0 %F OTHER: Local-ID: 462364EE2334C4A9C1257C60005317D1-Ramezani2013 %R 10.1007/978-3-642-38768-5_8 %D 2013 %B 19th International Conference on Computing and Combinatorics %Z date of event: 2013-06-21 - 2013-06-23 %C Hangzhou, China %B Computing and Combinatorics %E Du, Ding-Zhu; Zhang, Guochuan %P 65 - 76 %I Springer %@ 978-3-642-38767-8 %B Lecture Notes in Computer Science %N 7636 %@ false

%0 Journal Article %A Elmasry, Amr %A Mehlhorn, Kurt %A Schmidt, Jens M. %+ 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 Every DFS Tree of a 3-connected Graph Contains a Contractible Edge : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0015-78FA-7 %R 10.1002/jgt.21635 %F OTHER: Local-ID: 4FE50A6D333665B3C1257AC200498D2D-Elmasry2013 %7 2012-03 %D 2013 %J Journal of Graph Theory %V 72 %N 1 %& 112 %P 112 - 121 %I John Wiley & Sons. %C New York %@ false

%0 Conference Proceedings %A Huang, Chien-Chung %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Michail, Dimitrios %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Fair Matchings and Related Problems : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E46-7 %R 10.4230/LIPIcs.FSTTCS.2013.339 %U urn:nbn:de:0030-drops-43841 %D 2013 %B 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science %Z date of event: 2013-12-12 - 2013-12-14 %C Guwahati, India %B 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science %E Seth, Anil; Vishnoi, Nisheeth K. %P 339 - 350 %I Schloss Dagstuhl %@ 978-3-939897-64-4 %B Leibniz International Proceedings in Informatics %N 24 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2013/4384/

%0 Conference Proceedings %A Jurkiewicz, Tomasz %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Cost of Address Translation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0015-8656-6 %R 10.1137/1.9781611972931.13 %F OTHER: Local-ID: 8547751BA6E798C6C1257AD20051B773-VAT2013 %D 2013 %B 15th Meeting on Algorithm Engineering and Experiments %Z date of event: 2013-01-07 - 2013-01-07 %C New Orleans, LA, USA %X Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. In this paper, we address the computational cost of address translation in virtual memory. Starting point for our work is the observation that the analysis of some simple algorithms (random scan of an rray, binary search, heapsort) in either the RAM model or the EM model (external memory model) does not correctly predict growth rates of actual running times. We propose the VAT model (virtual address translation) to account for the cost of address translations and analyze the algorithms mentioned above and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC,Computer Science, Performance, cs.PF, %B Proceedings of the 15th Meeting on Algorithm Engineering and Experiments %E Sanders, Peter; Zeh, Norbert %P 148 - 162 %I SIAM %@ 978-1-61197-253-5

%0 Report %A Mehlhorn, Kurt %A Neumann, Adrian %A Schmidt, Jens M. %+ 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 Certifying 3-Edge-Connectivity : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-A622-F %U http://arxiv.org/abs/1211.6553 %D 2013 %8 04.11.2013 %X We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM

%0 Conference Proceedings %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Physarum Computations (Invited talk) : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E6E-D %U urn:nbn:de:0030-drops-39166 %R 10.4230/LIPIcs.STACS.2013.5 %D 2013 %8 18.02.2013 %B 30th International Symposium on Theoretical Aspects of Computer Science %Z date of event: 2013-02-27 - 2013-03-02 %C Kiel, Germany %B 30th International Symposium on Theoretical Aspects of Computer Science %E Portier, Natacha; Wilke, Thomas %P 5 - 6 %I Schloss Dagstuhl %@ 978-3-939897-50-7 %B Leibniz International Proceedings in Informatics %N 20 %U http://drops.dagstuhl.de/opus/volltexte/2013/3916/

%0 Conference Proceedings %E Mehlhorn, Kurt %E Vardi, Moshe Y. %E Herbstritt, Marc %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Publication Culture in Computing Research : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-A44B-5 %R 10.4230/DagRep.2.11.20 %U urn:nbn:de:0030-drops-39778 %D 2013 %8 25.03.2013 %B Dagstuhl Perspectives Workshop 12452 %Z date of event: 2012-11-06 - 2012-11-09 %D 2012 %C Wadern, Germany %K scholarly publishing, conference, journal, peer review, open archive, open access, indexing, research evaluation %S Dagstuhl Reports %V 2 %P 20 - 44 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2013/3977/

%0 Report %A Mehlhorn, Kurt %A Sagraloff, Michael %A Wang, Pengming %+ 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 From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0018-AB2E-0 %U http://arxiv.org/abs/1301.4870 %D 2013 %X We present an algorithm for isolating the roots of an arbitrary complex polynomial $p$ that also works for polynomials with multiple roots provided that the number $k$ of distinct roots is given as part of the input. It outputs $k$ pairwise disjoint disks each containing one of the distinct roots of $p$, and its multiplicity. The algorithm uses approximate factorization as a subroutine. In addition, we apply the new root isolation algorithm to a recent algorithm for computing the topology of a real planar algebraic curve specified as the zero set of a bivariate integer polynomial and for isolating the real solutions of a bivariate polynomial system. For input polynomials of degree $n$ and bitsize $\tau$, we improve the currently best running time from $\tO(n^{9}\tau+n^{8}\tau^{2})$ (deterministic) to $\tO(n^{6}+n^{5}\tau)$ (randomized) for topology computation and from $\tO(n^{8}+n^{7}\tau)$ (deterministic) to $\tO(n^{6}+n^{5}\tau)$ (randomized) for solving bivariate systems. %K Computer Science, Symbolic Computation, cs.SC

%0 Conference Proceedings %A Mehlhorn, Kurt %A Neumann, Adrian %A Schmidt, Jens M. %+ 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 Certifying 3-Edge-Connectivity : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0015-3EAD-B %R 10.1007/978-3-642-45043-3_31 %D 2013 %B 39th International Workshop on Graph-Theoretic Concepts in Computer Science %Z date of event: 2013-06-19 - 2013-06-21 %C L&#252;beck, Germany %B Graph-theoretic Concepts in Computer Science %E Brandst&#228;dt, Andreas; Jansen, Klaus; Reischuk, R&#252;diger %P 358 - 369 %I Springer %@ 978-3-642-45042-6 %B Lecture Notes in Computer Science %N 8165 %@ false

%0 Conference Proceedings %A Mehlhorn, Kurt %A Sagraloff, Michael %A Wang, Pengming %+ 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 From Approximate Factorization to Root Isolation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-444D-C %R 10.1145/2465506.2465523 %D 2013 %B 38th International Symposium on Symbolic and Algebraic Computation %Z date of event: 2013-06-26 - 2013-06-29 %C Boston, MA, USA %B ISSAC 2013 %E Kauers, Manuel %P 283 - 290 %I ACM %@ 978-1-4503-2059-7

%0 Report %A Sagraloff, Michael %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Computing Real Roots of Real Polynomials : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-4591-A %U http://arxiv.org/abs/1308.4088 %D 2013 %X Computing the real roots of a polynomial is a fundamental problem of computational algebra. We describe a variant of the Descartes method that isolates the real roots of any real square-free polynomial given through coefficient oracles. A coefficient oracle provides arbitrarily good approximations of the coefficients. The bit complexity of the algorithm matches the complexity of the best algorithm known, and the algorithm is simpler than this algorithm. The algorithm derives its speed from the combination of Descartes method with Newton iteration. Our algorithm can also be used to further refine the isolating intervals to an arbitrary small size. The complexity of root refinement is nearly optimal. %K Computer Science, Symbolic Computation, cs.SC,Computer Science, Numerical Analysis, cs.NA,Mathematics, Numerical Analysis, math.NA

%0 Journal Article %A Afshani, Peyman %A Agrawal, Manindra %A Doerr, Benjamin %A Larsen, Kasper Green %A Mehlhorn, Kurt %A Winzen, Carola %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Query Complexity of Finding a Hidden Permutation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0025-0634-2 %7 2012-11-05 %D 2012 %8 05.11.2012 %K Query complexity; randomized algorithms; guessing games; Mastermind %J Electronic Colloquium on Computational Complexity (ECCC) : Report Series %O ECCC %V 87 (Revision 1) %& 1 %P 1 - 36 %I Hasso-Plattner-Institut f&#252;r Softwaretechnik GmbH %C Potsdam %@ false %U http://eccc.hpi-web.de/report/2012/087/revision/1/download

%0 Journal Article %A Afshani, Peyman %A Agrawal, Manindra %A Doerr, Benjamin %A Larsen, Kasper Green %A Mehlhorn, Kurt %A Winzen, Carola %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Deterministic and Randomized Query Complexity of a Simple Guessing Game : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-A450-8 %7 2012 %D 2012 %K Query complexity; randomized algorithms; guessing games; Mastermind %J Electronic Colloquium on Computational Complexity (ECCC) : Report Series %O ECCC %V 87 %& 1 %P 1 - 33 %I Hasso-Plattner-Institut f&#252;r Softwaretechnik GmbH %C Potsdam %@ false %U http://eccc.hpi-web.de/report/2012/087/

%0 Conference Proceedings %A Bonifaci, Vincenzo %A Mehlhorn, Kurt %A Varma, Girish %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Physarum Can Compute Shortest Paths : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-BB81-8 %F OTHER: Local-ID: CA211EE0A1B815F8C1257AC200545CEC-Bonifaci2012a %D 2012 %B Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2012-01-17 - 2012-01-19 %C Kyoto, Japan %X Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s_0 and s_1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s_0-s_1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years. %B Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms %E Ravani, Yuval %P 233 - 240 %I SIAM %@ 978-1-611972-11-5

%0 Journal Article %A Bonifaci, Vincenzo %A Mehlhorn, Kurt %A Varma, Girish %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Physarum Can Compute Shortest Paths : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-C4DA-A %R 10.1016/j.jtbi.2012.06.017 %F OTHER: Local-ID: 2E63427366C2D939C1257AC2005DC800-Bonifaci2012c %7 2012-06-22 %D 2012 %X Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s_0 and s_1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s_0-s_1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years. %K slime mold, natural algorithm, natural adaptive networks %J Journal of Theoretical Biology %V 309 %& 121 %P 121 - 133 %I Elsevier %C Amsterdam %@ false

%0 Report %A Bringmann, Karl %A Mehlhorn, Kurt %A Neumann, Adrian %+ 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 Remarks on Category-based Routing in Social Networks : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0018-AB51-B %U http://arxiv.org/abs/1202.2293 %D 2012 %X It is well known that individuals can route messages on short paths through social networks, given only simple information about the target and using only local knowledge about the topology. Sociologists conjecture that people find routes greedily by passing the message to an acquaintance that has more in common with the target than themselves, e.g. if a dentist in Saarbr\"ucken wants to send a message to a specific lawyer in Munich, he may forward it to someone who is a lawyer and/or lives in Munich. Modelling this setting, Eppstein et al. introduced the notion of category-based routing. The goal is to assign a set of categories to each node of a graph such that greedy routing is possible. By proving bounds on the number of categories a node has to be in we can argue about the plausibility of the underlying sociological model. In this paper we substantially improve the upper bounds introduced by Eppstein et al. and prove new lower bounds. %K cs.SI,Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Discrete Mathematics, cs.DM, Physics, Physics and Society, physics.soc-ph

%0 Conference Proceedings %A Bringmann, Karl %A Panagiotou, Konstantinos %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Efficient Sampling Methods for Discrete Distributions : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-BBDB-2 %R 10.1007/978-3-642-31594-7_12 %F OTHER: Local-ID: 76C613922FECC644C1257AD300348137-BringmannP12 %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-07-09 - 2012-07-13 %C Warwick, UK %X We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities p_1,...,p_n. We consider the problem of sampling a subset, which includes the i-th event independently with probability p_i, and the problem of sampling from the distribution, where the i-th event has a probability proportional to p_i. For both problems we present on two different classes of inputs &#65533; sorted and general probabilities &#65533; efficient preprocessing algorithms that allow for asymptotically optimal querying, and prove almost matching lower bounds for their complexity. %B Automata, Languages, and Programming %E Czumaj, Artur; Mehlhorn, Kurt; Pitts, Andrew M.; Wattenhofer, Roger %P 133 - 144 %I Springer %@ 978-3-642-31593-0 %B Lecture Notes in Computer Science %N 7391 %@ false

%0 Conference Proceedings %A Cygan, Marek %A Kratsch, Stefan %A Pilipczuk, Marcin %A Pilipczuk, Micha %A Wahlstr&#246;m, Magnus %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Clique Cover and Graph Separation: New Incompressibility Results : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-BC4B-B %R 10.1007/978-3-642-31594-7_22 %F OTHER: Local-ID: 5A998CDCF7D0A3FCC1257AD4004D05AF-CyganKratschPilipczukPilipczukWahlstroem2012 %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-07-09 - 2012-07-13 %C Warwick, UK %B Automata, Languages, and Programming %E Czumaj, Artur; Mehlhorn, Kurt; Pitts, Andrew M.; Wattenhofer, Roger %P 254 - 265 %I Springer %@ 978-3-642-31593-0 %B Lecture Notes in Computer Science %Y Czumaj, Artur; Mehlhorn, Kurt; Pitts, Andrew; Wattenhofer, Roger %N 7391 %@ false

%0 Conference Proceedings %E Czumaj, Artur %E Mehlhorn, Kurt %E Pitts, Andrew %E Wattenhofer, Roger %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Automata, Languages, and Programming : 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-A441-A %R 10.1007/978-3-642-31585-5 %@ 978-3-642-31584-8 %I Springer %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-07-09 - 2012-07-13 %D 2012 %C Warwick, UK %S Lecture Notes in Computer Science %V 7392 %@ false

%0 Conference Proceedings %E Czumaj, Artur %E Mehlhorn, Kurt %E Pitts, Andrew %E Wattenhofer, Roger %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Automata, Languages, and Programming : 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-A43E-3 %R 10.1007/978-3-642-31594-7 %@ 978-3-642-31593-0 %I Springer %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-07-09 - 2012-07-13 %D 2012 %C Warwick, UK %S Lecture Notes in Computer Science %V 7391 %@ false

%0 Conference Proceedings %A Elbassioni, Khaled %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A QPTAS for &#949;-Envy-free Profit-maximizing Pricing on Line Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-BC8C-A %R 10.1007/978-3-642-31585-5_46 %F OTHER: Local-ID: 140EF868CCF427F9C1257AD40047FB11-Elbassioni2012e %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-07-09 - 2012-07-13 %C Warwick, UK %B Automata, Languages, and Programming %E Czumaj, Artur; Mehlhorn, Kurt; Pitts, Andrew M.; Wattenhofer, Roger %P 513 - 524 %I Springer %@ 978-3-642-31584-8 978-3-642-31585-5 %B Lecture Notes in Computer Science %N 7392

%0 Journal Article %A Elmasry, Amr %A Mehlhorn, Kurt %A Schmidt, Jens M. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T An O(n+ m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-15F9-4 %F EDOC: 536712 %R 10.1007/s00453-010-9481-2 %F OTHER: Local-ID: C1256428004B93B8-A45F18DF4E1C7C57C1257846003F6ADF-ElmasryMehlhornSchmidt2010 %7 2010 %D 2012 %J Algorithmica %V 62 %N 3 %& 754 %P 754 - 766 %I Springer %C New York, NY %@ false

%0 Report %A Jurkiewicz, Tomasz %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Cost of Address Translation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0015-8653-C %U http://arxiv.org/abs/1212.0703 %D 2012 %X Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. In this paper, we address the computational cost of address translation in virtual memory. Starting point for our work is the observation that the analysis of some simple algorithms (random scan of an array, binary search, heapsort) in either the RAM model or the EM model (external memory model) does not correctly predict growth rates of actual running times. We propose the VAT model (virtual address translation) to account for the cost of address translations and analyze the algorithms mentioned above and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC,Computer Science, Performance, cs.PF,

%0 Conference Proceedings %A Kane, Daniel %A Mehlhorn, Kurt %A Sauerwald, Thomas %A Sun, He %+ 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 Counting Arbitrary Subgraphs in Data Streams : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-BDD7-D %R 10.1007/978-3-642-31585-5 %F OTHER: Local-ID: D59F81728CEDD0B9C1257AD000568326-Sun2012b %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-07-09 - 2012-07-13 %C Warwick, UK %B Automata, Languages, and Programming %E Czumaj, Artur; Mehlhorn, Kurt; Pitts, Andrew M.; Wattenhofer, Roger %P 598 - 609 %I Springer %@ 978-3-642-31584-8 %B Lecture Notes in Computer Science %N 7392 %@ false

%0 Conference Proceedings %A Kratsch, Stefan %A Pilipczuk, Marcin %A Pilipczuk, Micha %A Wahlstr&#246;m, Magnus %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fixed-parameter Tractability of Multicut in Directed Acyclic Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-BE86-C %R 10.1007/978-3-642-31594-7_49 %F OTHER: Local-ID: E10E3826E7217AEBC1257AD4004D690C-KratschPilipczukPilipczukWahlstroem2012 %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-07-09 - 2012-07-13 %C Warwick, UK %B Automata, Languages, and Programming %E Czumaj, Artur; Mehlhorn, Kurt; Pitts, Andrew M.; Wattenhofer, Roger %P 581 - 593 %I Springer %@ 978-3-642-31593-0 %B Lecture Notes in Computer Science %N 7391 %@ false

%0 Journal Article %A Megow, Nicole %A Mehlhorn, Kurt %A Schweitzer, Pascal %+ 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 Online Graph Exploration: New Results on Old and New Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-C49C-7 %R 10.1016/j.tcs.2012.06.034 %F OTHER: Local-ID: 18D093BE87A59A63C1257AC5007EF50F-MegowMehlhornSchweitzer2012 %7 2012-07-08 %D 2012 %J Theoretical Computer Science %V 463 %& 62 %P 62 - 72 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Megow, Nicole %A Skutella, Martin %A Verschae, Jose %A Wiese, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Power of Recourse for Online MST and TSP : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-BE8E-B %R 10.1007/978-3-642-31594-7_58 %F OTHER: Local-ID: F9D0FE85F8D1AF2FC1257AC5007D0CF8-MegowSVW2012 %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-11-29 - 2012-11-29 %C Warwick %B Automata, Languages, and Programming %E Czumaj, Artur; Mehlhorn, Kurt; Pitts, Andrew M.; Wattenhofer, Roger %P 689 - 700 %I Springer %@ 978-3-642-31593-0 %B Lecture Notes in Computer Science %N 7391 %@ false

%0 Journal Article %A Mehlhorn, Kurt %A Sack, Joerg-Ruediger %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T CGTA-Awards 2011 : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-5E87-4 %R 10.1016/j.comgeo.2011.11.005 %7 2012 %D 2012 %J Computational Geometry: Theory and Applications %V 45 %N 4 %& 139 %P 139 - 139 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Schmidt, Jens M. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Certifying 3-Connectivity in Linear Time : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0014-BEEC-6 %R 10.1007/978-3-642-31594-7_66 %F OTHER: Local-ID: 9F99A9B8CE9D07A0C1257AC2004AE457-Schmidt2012b %D 2012 %B 39th International Colloquium on Automata, Languages, and Programming %Z date of event: 2012-07-09 - 2012-07-13 %C Warwick, UK %B Automata, Languages, and Programming %E Czumaj, Artur; Mehlhorn, Kurt; Pitts, Andrew; Wattenhofer, Roger %P 786 - 797 %I Springer %@ 978-3-642-31593-0 %B Lecture Notes in Computer Science %N 7391 %@ false

%0 Conference Proceedings %A Alkassar, Eyad %A B&#246;hme, Sascha %A Mehlhorn, Kurt %A Rizkallah, Christine %+ Cluster of Excellence Multimodal Computing and Interaction External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Verification of Certifying Computations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0010-12BF-E %F EDOC: 618673 %R 10.1007/978-3-642-22110-1_7 %U http://www.mpi-inf.mpg.de/~mehlhorn/ftp/VerificationCertComps.pdf %F OTHER: Local-ID: C1256428004B93B8-5C01AA7BBEAB7C26C125785C003095BF-FormalVerificationofCertifyingComputations %D 2011 %B CAV 2011 %Z date of event: 2011-07-14 - 2011-07-20 %C Snowbird, Utah, USA %X Formal verification of complex algorithms is challenging. Verifying their implementations goes beyond the state of the art of current verification tools and proving their correctness usually involves non-trivial mathematical theorems. Certifying algorithms compute in addition to each output a witness certifying that the output is correct. A checker for such a witness is usually much simpler than the original algorithm -- yet it is all the user has to trust. Verification of checkers is feasible with current tools and leads to computations that can be completely trusted. In this paper we develop a framework to seamlessly verify certifying computations. The automatic verifier VCC is used for checking code correctness, and the interactive theorem prover Isabelle/HOL targets high-level mathematical properties of algorithms. We demonstrate the effectiveness of our approach by applying it to the verification of the algorithmic library LEDA. %B Computer Aided Verification %E Gopalakrishnan, Ganesh; Qadeer, Shaz %P 67 - 82 %I Springer %@ 978-3-642-22109-5 %B Lecture Notes in Computer Science %N 6806

%0 Journal Article %A Alkassar, Eyad %A B&#246;hme, Sascha %A Mehlhorn, Kurt %A Rizkallah, Christine %A Schweitzer, Pascal %+ International Max Planck Research School, 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T An Introduction to Certifying Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-A46F-6 %7 2011 %D 2011 %J Information technology %O it %V 53 %N 6 %& 287 %P 287 - 293 %I Oldenbourg Wissenschaftsverlag %C M&#252;nchen %@ false

%0 Report %A Amaldi, Edoardo %A Iuliano, Claudio %A Jurkiewicz, Tomasz %A Mehlhorn, Kurt %A Rizzi, Romeo %+ 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 Improved Minimum Cycle Bases Algorithms by Restriction to Isometric Cycles : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-4C4C-D %D 2011

%0 Journal Article %A Baswana, Surender %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Pettie, Seth %+ 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 %T Additive Spanners and (&#945;, &#946;)-Spanners : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0010-11D8-B %F EDOC: 618744 %R 10.1145/1868237.1868242 %U http://doi.acm.org/10.1145/1868237.1868242 %F OTHER: Local-ID: C1256428004B93B8-150FC93C5EEE2627C12579C90051FFA8-MehlhornTALG2011 %7 2011 %D 2011 %* Review method: peer-reviewed %J ACM Transactions on Algorithms %V 7 %N 1 %& 5:1 %P 5:1 - 5:26 %Z sequence number: 5 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Christodoulou, George %A Mehlhorn, Kurt %A Pyrga, Evangelia %+ 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 Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0010-1240-6 %F EDOC: 618742 %R 10.1007/978-3-642-23719-5_11 %U http://dx.doi.org/10.1007/978-3-642-23719-5_11 %F OTHER: Local-ID: C1256428004B93B8-D203A9C35EF58BBAC12579A3004010FD-Becker2011 %D 2011 %B 19th Annual European Symposium on %Z date of event: 2011-09-05 - 2011-09-09 %C Saarbr&#252;cken, Germany %B Algorithms - ESA 2011 %E Demetrescu, Camil; Halld&#243;rsson, Mang&#250;s M. %P 119 - 130 %I Springer %@ 978-3-642-23718-8 %B Lecture Notes in Computer Science %N 6942

%0 Book Section %A Eigenwillig, Arno %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Multiplication of Long Integers -- Faster than Long Multiplication : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-4C8F-8 %R 10.1007/978-3-642-15328-0_11 %D 2011 %B Algorithms Unplugged %E V&#246;cking, Berthold; Alt, Helmut; Dietzfelbinger, Martin; Reischuk, R&#252;diger; Scheideler, Christian; Vollmer, Heribert; Wagner, Dorothea %P 101 - 109 %I Springer %C Berlin %@ 978-3-642-15327-3

%0 Journal Article %A Halperin, Dan %A Mehlhorn, Kurt %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Guest Editorial: Selected Papers from European Symposium on Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0024-A469-1 %7 2011 %D 2011 %J Algorithmica %V 60 %N 1 %& 1 %P 1 - 2 %I Springer %C New York, NY %@ false

%0 Journal Article %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Michail, Dimitrios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T New Approximation Algorithms for Minimum Cycle Bases of Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0010-125C-A %F EDOC: 618754 %R 10.1007/s00453-009-9313-4 %U http://dx.doi.org/10.1007/s00453-009-9313-4 %F OTHER: Local-ID: C1256428004B93B8-9DF47B615A95B3B9C12579CA0043E5C0-KavithaALG2011 %D 2011 %* Review method: peer-reviewed %J Algorithmica %V 59 %N 4 %& 471 %P 471 - 488 %I Springer %C New York, NY %@ false

%0 Conference Proceedings %A Manjunath, Madhusudan %A Mehlhorn, Kurt %A Panagiotou, Konstantinos %A Sun, He %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Approximate Counting of Cycles in Streams : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0019-85DB-D %R 10.1007/978-3-642-23719-5_57 %D 2011 %B ESA 2011 %Z date of event: - %B Algorithms &#8211; ESA 2011 %E Demetrescu, Camil; M. Halld&#243;rsson, Magn&#250;s %P 677 - 688 %I Springer %B Lecture Notes in Computer Science %N 6942

%0 Conference Proceedings %A Megow, Nicole %A Mehlhorn, Kurt %A Schweitzer, Pascal %+ 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 Online Graph Exploration: New Results on Old and New Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0010-1266-3 %F EDOC: 618681 %R 10.1007/978-3-642-22012-8_38 %U http://dx.doi.org/10.1007/978-3-642-22012-8_38 %F OTHER: Local-ID: C1256428004B93B8-19606035D4D26455C12578810025513C-Megow2011-explore %D 2011 %B 38th International Colloquium on Automata, Languages and Programming %Z date of event: 2011-07-04 - 2011-07-08 %C Zurich, Switzerland %B Automata, Languages and Programming %E Aceto, Luca; Henzinger, Monika; Sgall, Ji&#345;&#237; %P 478 - 489 %I Springer %@ 978-3-642-22011-1 %B Lecture Notes in Computer Science %N 6756

%0 Journal Article %A Mehlhorn, Kurt %A Sagraloff, Michael %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Deterministic Algorithm for Isolating Real Roots of a Real Polynomial : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0010-11DA-7 %F EDOC: 618656 %R 10.1016/j.jsc.2010.09.004 %U http://dx.doi.org/10.1016/j.jsc.2010.09.004 %F OTHER: Local-ID: C1256428004B93B8-A0FD28893140854AC125781C003E51F3-MS:Bistream:2011 %7 2011 %D 2011 %* Review method: peer-reviewed %X We describe a bisection algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is simpler, deterministic and has better asymptotic complexity than the randomized algorithm of Eigenwillig et al. (2005). We also discuss a partial extension to multiple roots. %J Journal of Symbolic Computation %V 46 %N 1 %& 70 %P 70 - 90 %I Elsevier %C Amsterdam

%0 Journal Article %A Mehlhorn, Kurt %A Osbild, Ralf %A Sagraloff, Michael %+ 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 A General Approach to the Analysis of Controlled Perturbation Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0010-11DC-3 %F EDOC: 618677 %R 10.1016/j.comgeo.2011.06.001 %U http://dx.doi.org/10.1016/j.comgeo.2011.06.001 %F OTHER: Local-ID: C1256428004B93B8-2A5C0FDF3B7C1B18C1257861003B9A82-MOS-CP2011 %7 2011 %D 2011 %* Review method: peer-reviewed %J Computational Geometry %V 44 %N 9 %& 507 %P 507 - 528 %I Elsevier %C Amsterdam

%0 Journal Article %A Shervashidze, Nino %A Schweitzer, Pascal %A van Leeuwen, Erik Jan %A Mehlhorn, Kurt %A Borgwardt, Karsten M. %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Weisfeiler-Lehman Graph Kernels : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0010-12C2-4 %F EDOC: 618759 %F OTHER: Local-ID: C1256428004B93B8-11F8B9324866AC60C12579CA004E38AC-Shervashidze2011 %7 2011 %D 2011 %* Review method: peer-reviewed %J Journal of Machine Learning Research %V 12 %& 2539 %P 2539 - 2561 %I MIT Press %C Cambridge, Mass. %@ false

%0 Journal Article %A Berberich, Eric %A Fogel, Efi %A Halperin, Dan %A Mehlhorn, Kurt %A Wein, Ron %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Arrangements on Parametric Surfaces I: General Framework and Infrastructure : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-160D-0 %F EDOC: 536751 %R 10.1007/s11786-010-0042-5 %U http://www.springerlink.com/content/gg0px81230557612/ %F OTHER: Local-ID: C1256428004B93B8-745F1A8BE751371AC12577FB002DE576-bfhmw-aos1-2010 %D 2010 %* Review method: peer-reviewed %J Mathematics in Computer Science %V 4 %N 1 %& 45 %P 45 - 66 %I Springer %C Berlin %@ false

%0 Journal Article %A Garg, Naveen %A Kavitha, T. %A Kumar, Amit %A Mehlhorn, Kurt %A Mestre, Juli&#225;n %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Assigning Papers to Referees : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1611-4 %F EDOC: 536729 %R 10.1007/s00453-009-9386-0 %U http://dx.doi.org/10.1007/s00453-009-9386-0 %F OTHER: Local-ID: C1256428004B93B8-213E0759D254F459C12576C500583EE4-MehlhonMestre2009 %7 2010 %D 2010 %* Review method: peer-reviewed %J Algorithmica %V 58 %N 1 %& 119 %P 119 - 136 %I Springer %C New York, NY %@ false

%0 Journal Article %A McConnell, Ross M. %A Mehlhorn, Kurt %A N&#228;her, Stefan %A Schweitzer, Pascal %+ 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 Certifying Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1624-9 %F EDOC: 536711 %R 10.1016/j.cosrev.2010.09.009 %U http://dx.doi.org/10.1016/j.cosrev.2010.09.009 %F OTHER: Local-ID: C1256428004B93B8-3814D1CC91136BA8C1257846003BA54F-McConnell2010 %7 2010 %D 2010 %J Computer Science Review %V 5 %N 2 %& 119 %P 119 - 161 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Mehlhorn, Kurt %A Schweitzer, Pascal %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Progress on Certifying Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-16C0-9 %F EDOC: 536774 %R 10.1007/978-3-642-14553-7_1 %U http://dx.doi.org/10.1007/978-3-642-14553-7_1 %F OTHER: Local-ID: C1256428004B93B8-6ADD7B6CDB83F33EC125781800375471-MehlhornSchweitzer2010 %D 2010 %B 4th International Workshop on Frontiers in Algorithmics %Z date of event: 2010-08-11 - 2010-08-13 %C Wuhan, China %B Frontiers in Algorithmics %E Lee, Der-Tsai; Chen, Danny Z.; Ying, Shi %P 1 - 5 %I Springer %@ 978-3-642-14552-0 %B Lecture Notes in Computer Science %N 6213

%0 Journal Article %A Mehlhorn, Kurt %A Ray, Saurabh %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Algorithms for Computing Hong&#8217;s Bound on Absolute Positiveness : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1653-1 %F EDOC: 536776 %R 10.1016/j.jsc.2010.02.002 %U http://dx.doi.org/10.1016/j.jsc.2010.02.002 %F OTHER: Local-ID: C1256428004B93B8-F2A3B1100AA47E69C125781800385310-MehlhornRay2010 %7 2010 %D 2010 %* Review method: peer-reviewed %J Journal of Symbolic Computation %V 45 %N 6 %& 677 %P 677 - 683 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Reliable and Efficient Geometric Computing : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-16CC-2 %F EDOC: 536767 %R 10.1007/978-3-642-15582-6_3 %U http://dx.doi.org/10.1007/978-3-642-15582-6_3 %F OTHER: Local-ID: C1256428004B93B8-ECD1954FEE1EB130C125781700444D74-Mehlhorn2010 %D 2010 %B Third International Congress on Mathematical Software %Z date of event: 2010-09-13 - 2010-09-17 %C Kobe, Japan %B Mathematical Software %E Fukuda, Komei; Van der Hoeven, Joris; Joswig, Michael; Takayama, Nobuki %P 10 - 11 %I Springer %@ 978-3-642-15581-9 %B Lecture Notes in Computer Science %N 6327

%0 Conference Proceedings %A Amaldi, Edoardo %A Iuliano, Claudio %A Jurkiewicz, Tomasz %A Mehlhorn, Kurt %A Rizzi, Romeo %+ 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 Breaking the O(m^2n) Barrier for Minimum Cycle Bases : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0019-DA98-1 %R 10.1007/978-3-642-04128-0_28 %D 2009 %B 17th Annual European Symposium on Algorithms %Z date of event: 2009-09-07 - 2009-09-09 %C Copenhagen, Denmark %B Algorithms - ESA 2009 %E Fiat, Amos; Sanders, Peter %P 301 - 312 %I Springer %@ 978-3-642-04127-3 %B Lecture Notes in Computer Science %N 5757

%0 Journal Article %A Burnikel, Christoph %A Funke, Stefan %A Mehlhorn, Kurt %A Schirra, Stefan %A Schmitt, Susanne %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Separation Bound for Real Algebraic Expressions : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-4E36-9 %R 10.1007/s00453-007-9132-4 %7 2007 %D 2009 %J Algorithmica %V 55 %& 14 %P 14 - 28 %I Springer-Verlag %C New York %@ false

%0 Journal Article %A Kavitha, T. %A Liebchen, Ch. %A Mehlhorn, Kurt %A Michail, Dimitrios %A Rizzi, R. %A Ueckerdt, T. %A Zweig, K. %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Cycle Bases in Graphs: Characterization, Algorithms, Complexity, and Applications : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1829-2 %F EDOC: 518293 %F OTHER: Local-ID: C1256428004B93B8-804B2DD468A04320C1257585005C05FE-SurveyCycleBases %R 10.1016/j.cosrev.2009.08.001 %D 2009 %J Computer Science Review %V 3 %N 4 %& 199 %P 199 - 243 %I Elsevier %C Amsterdam

%0 Journal Article %A Mehlhorn, Kurt %A Michail, Dimitrios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Minimum Cycle Bases: Faster and Simpler : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-187C-6 %F EDOC: 518294 %F OTHER: Local-ID: C1256428004B93B8-2A4064B111CA0E04C1257585005CC8E1-CycleBasisSimplified %R 10.1145/1644015.1644023 %D 2009 %* Review method: peer-reviewed %J ACM Transactions on Algorithms %O TALG %V 6 %N 1 %& 8:1 %P 8:1 - 8:13 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Mehlhorn, Kurt %A Sagraloff, Michael %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Isolating Real Roots of Real Polynomials : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-17F2-2 %F EDOC: 518292 %F OTHER: Local-ID: C1256428004B93B8-AE8C9A24B63BC4A8C125759E0029B4A4-ms-detbitdesc-09 %R 10.1145/1576702.1576737 %D 2009 %B 2009 International Symposium on Symbolic and Algebraic Computation %Z date of event: 2009-07-28 - 2009-07-31 %C Seoul, Korea %X We describe a Descartes algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients of the polynomial can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is deterministic and has almost the same asymptotic complexity as the randomized bitstream-Descartes algorithm of~\citet{BitstreamDescartes}. Besides being deterministic, the algorithm is also somewhat simpler to analyze. %B Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation %P 247 - 254 %I ACM %@ 978-1-60558-609-0

%0 Conference Proceedings %A Sherashidze, Nino %A Vishwanathan, S. V. N. %A Petri, Tobias H. %A Mehlhorn, Kurt %A Borgwardt, Karsten M. %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Efficient Graphlet Kernels for Large Graph Comparison : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1834-8 %F EDOC: 518242 %F OTHER: Local-ID: C1256428004B93B8-43BA02F2485CFBF4C1257585005B4454-Graphlets %D 2009 %B 12th International Conference on Artificial Intelligence and Statistics %Z date of event: 2009-03-26 - 2009-03-26 %C Clearwater Beach, FL, USA %B 12th International Conference on Artificial Intelligence and Statistics %E van Dyk, David; Welling, Max %P 488 - 495 %I Society for Artificial Intelligence and Statistics %B Proceedings of Machine Learning Research %N 5 %U http://proceedings.mlr.press/v5/shervashidze09a/shervashidze09a.pdf

%0 Conference Proceedings %A Angelopoulos, Spyros %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1ADF-9 %F EDOC: 427974 %R 10.1007/978-3-540-87744-8_7 %F OTHER: Local-ID: C125756E0038A185-3EB6F5B2FD7D2467C1257551004AD9C1-Ang:08.steiner %D 2008 %B 16th Annual European Symposium on %Z date of event: 2008-09-15 - 2008-09-17 %C Karlsruhe, Germany %B Algorithms - ESA 2008 %E Halperin, Dan; Mehlhorn, Kurt %P 76 - 87 %I Springer %@ 978-3-540-87743-1 %B Lecture Notes in Computer Science %N 5193

%0 Conference Proceedings %A Christodoulou, George %A Koutsoupias, Elias %A Vidali, Angelina %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Characterization of 2-Player Mechanisms for Scheduling : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1ABE-4 %F EDOC: 428015 %R 10.1007/978-3-540-87744-8 %F OTHER: Local-ID: C125756E0038A185-2E4C37A8576707E2C125753A006C38D1-ChristodoulouKV2008 %D 2008 %B 16th Annual European Symposium on Algorithms %Z date of event: 2008-09-15 - 2008-09-17 %C Karlsruhe, Germany %B Algorithms - ESA 2008 %E Halperin, Dan; Mehlhorn, Kurt %P 297 - 307 %I Springer %@ 978-3-540-87743-1 %B Lecture Notes in Computer Science %N 5193

%0 Book Section %A Eigenwillig, Arno %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Multiplikation langer Zahlen (schneller als in der Schule) : %G deu %U http://hdl.handle.net/11858/00-001M-0000-000F-1D6A-C %F EDOC: 572238 %R 10.1007/978-3-540-76393-2 %D 2008 %B Taschenbuch der Algorithmen %E V&#246;cking, Berthold; Alt, Helmut; Dietzfelbinger, Martin; Reischuk, R&#252;diger; Scheideler, Christian; Vollmer, Heribert; Wagner, Dorothea %P 109 - 118 %I Springer %C Berlin %@ 978-3-540-76393-2

%0 Conference Proceedings %E Halperin, Dan %E Mehlhorn, Kurt %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Algorithms - ESA 2008 : 16th Annual European Symposium : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1AD1-5 %F EDOC: 428098 %@ 978-3-540-87743-1 %R 10.1007/978-3-540-87744-8 %F OTHER: Local-ID: C125756E0038A185-14FFC212583C3355C1257571003AEB16-Mehlhorn08 %I Springer %D 2008 %B 16th Annual European Symposium on Algorithms %Z date of event: 2008-09-15 - 2008-09-17 %D 2008 %C Karlsruhe, Germany %P XVII, 844

%0 Journal Article %A Hariharan, Ramesh %A Kavitha, Telikepalli %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Algorithms for Minimum Cycle Basis in Directed Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1BA5-1 %F EDOC: 428101 %R 10.1137/060670730 %U http://dx.doi.org/10.1137/060670730 %F OTHER: Local-ID: C125756E0038A185-790E08A3736682E2C125757800338B00-Hariharan2008 %7 2008 %D 2008 %* Review method: peer-reviewed %J SIAM Journal on Computing %V 38 %N 4 %& 1430 %P 1430 - 1447 %I SIAM %C Philadelphia, PA %@ false

%0 Journal Article %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Michail, Dimitrios %A Paluch, Katarzyna E. %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T An O&#732; (m2n) Algorithm for Minimum Cycle Basis of Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1AEB-D %F EDOC: 428121 %R 10.1007/s00453-007-9064-z %F OTHER: Local-ID: C125756E0038A185-7AA9BDC617A56BE7C125757800420759-Kavitha2008 %7 2008 %D 2008 %* Review method: peer-reviewed %J Algorithmica %V 52 %N 3 %& 333 %P 333 - 349 %I Springer %C New York %@ false

%0 Journal Article %A Kettner, Lutz %A Mehlhorn, Kurt %A Pion, Sylvain %A Schirra, Stefan %A Yap, Chee %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Classroom Examples of Robustness Problems in Geometric Computations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1B35-C %F EDOC: 428123 %R 10.1016/j.comgeo.2007.06.003 %U http://dx.doi.org/10.1016/j.comgeo.2007.06.003 %F OTHER: Local-ID: C125756E0038A185-113F896EB9E35B7AC12573E60045601C-Kettner2007Classroom %7 2008 %D 2008 %* Review method: peer-reviewed %J Computational Geometry: Theory and Applications %V 40 %N 1 %& 61 %P 61 - 78 %I Elsevier %C Amsterdam %@ false

%0 Book %A Mehlhorn, Kurt %A Sanders, Peter %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Algorithms and Data Structures: The Basic Toolbox : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-17F9-3 %F EDOC: 518298 %R 10.1007/978-3-540-77978-0 %@ 978-3-540-77977-3 %F OTHER: Local-ID: C1256428004B93B8-75AD1CF772C0FE5BC12575850043645F-Mehlhorn-Sanders:Toolbox %I Springer %C Berlin %D 2008 %P 300

%0 Journal Article %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Deterministic and Randomized Algorithms for Minimum Cycle Basis in Directed Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1BA7-E %F EDOC: 428164 %U http://www.mpi-inf.mpg.de/~mehlhorn/ftp/DirectedCycleBasisJournal.pdf %F OTHER: Local-ID: C125756E0038A185-2E4A966E27BF5CF7C125755B004DA137-Mehlhorn2008b %R 10.1137/060670730 %D 2008 %* Review method: peer-reviewed %J SIAM Journal of Computing %V 38 %N 4 %& 1430 %P 1430 - 1447 %@ false

%0 Journal Article %A Abraham, David J. %A Irving, Robert W. %A Kavitha, Telikepalli %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Popular Matchings : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-2059-8 %F EDOC: 356652 %R 10.1137/06067328X %F OTHER: Local-ID: C12573CC004A8E26-6B07E5D0BA1AD3E5C12573E70031E1C4-Abraham2007Popular %7 2007 %D 2007 %* Review method: peer-reviewed %J SIAM Journal on Computing %V 37 %N 4 %& 1030 %P 1030 - 1045 %I SIAM %C Philadelphia, PA %@ false

%0 Conference Proceedings %A Berberich, Eric %A Fogel, Efi %A Halperin, Dan %A Mehlhorn, Kurt %A Wein, Ron %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sweeping and Maintaining two-dimensional Arrangements on Surfaces: A First Step : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-20E9-6 %F EDOC: 356662 %R 10.1007/978-3-540-75520-3_57 %F OTHER: Local-ID: C12573CC004A8E26-5496A47512AF3FBEC12573D1004BD408-bfhmw-samtdaosafs-07 %D 2007 %B 15th Annual European Symposium on Algorithms %Z date of event: 2007-10-08 - 2007-10-10 %C Eilat, Israel %B Algorithms - ESA 2007 %E Arge, Lars; Hoffmann, Michael; Welzl, Emo %P 645 - 656 %I Springer %@ 978-3-540-75519-7 %B Lecture Notes in Computer Science %N 4698

%0 Report %A Berberich, Eric %A Fogel, Efi %A Halperin, Dan %A Mehlhorn, Kurt %A Wein, Ron %+ 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 Sweeping and maintaining two-dimensional arrangements on quadrics : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-20E3-1 %F EDOC: 356692 %F OTHER: Local-ID: C12573CC004A8E26-A2D9FC191F294C4BC12573D1004D4FA3-acs:bfhmw-smtaoq-07 %Y University of Groningen %C Groningen, The Netherlands %D 2007 %P 10 p. %B ACS Technical Reports

%0 Journal Article %A Gotsman, Craig %A Kaligosi, Kanela %A Mehlhorn, Kurt %A Michail, Dimitrios %A Pyrga, Evangelia %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Cycle Bases of Graphs and Sampled Manifolds : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1EC9-C %F EDOC: 356742 %R 10.1016/j.cagd.2006.07.001 %F OTHER: Local-ID: C12573CC004A8E26-CE8DCB4C127284AAC125728E003EFD6F-GKMMP06 %7 2007 %D 2007 %* Review method: peer-reviewed %J Computer Aided Geometric Design %V 24 %N 8/9 %& 464 %P 464 - 480 %I North-Holland %C Amsterdam %@ false

%0 Journal Article %A Hachenberger, Peter %A Kettner, Lutz %A 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 Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, Optimized Implementation and Experiments : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1E75-A %F EDOC: 356713 %R 10.1016/j.comgeo.2006.11.009 %F OTHER: Local-ID: C12573CC004A8E26-FECC77F07C1A1E72C12573D20003E1DD-Kettner2007Nef3 %7 2007 %D 2007 %* Review method: peer-reviewed %J Computational Geometry: Theory and Applications %V 38 %N 1-2 %& 64 %P 64 - 99 %I Elsevier %C Amsterdam %@ false

%0 Journal Article %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Michail, Dimitrios %A Paluch, Katarzyna E. %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-residents Problem : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-20CE-4 %F EDOC: 356670 %R 10.1145/1240233.1240238 %F OTHER: Local-ID: C12573CC004A8E26-C2986B86FD6341EBC12573CA0030895C-a15-kavitha %7 2007 %D 2007 %* Review method: peer-reviewed %J ACM Transactions on Algorithms %V 3 %N 2 %& 15.1 %P 15.1 - 15.18 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Michail, Dimitrios %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T New Approximation Algorithms for Minimum Cycle Bases of Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-2001-E %F EDOC: 356750 %R 10.1007/978-3-540-70918-3_44 %F OTHER: Local-ID: C12573CC004A8E26-2BFAB74EC24AD32DC125728E003EAFF1-KMM07 %D 2007 %B 24th Annual Symposium on Theoretical Aspects of Computer Science %Z date of event: 2007-02-22 - 2007-02-24 %C Aachen, Germany %X We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g.&#160;the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k&#8201;&#8805;&#8201;1, we give (2k&#8201;&#8722;&#8201;1)-approximation algorithms with expected running time O(k m n1&#8201;+&#8201;2/k&#8201;+&#8201;m n(1&#8201;+&#8201;1/k)(&#969;&#8201;&#8722;&#8201;1)) and deterministic running time O( n3&#8201;+&#8201;2/k ), respectively. Here &#969; is the best exponent of matrix multiplication. It is presently known that &#969;&#8201;&lt;&#8201;2.376. Both algorithms are o( m&#969; ) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the &#920;(m&#969;) bound. We also present a 2-approximation algorithm with expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n3) time 2.42-approximation algorithm for the complete Euclidean graph in the plane. %B STACS 2007 %E Thomas, Wolfgang; Weil, Pascal %P 512 - 523 %I Springer %@ 978-3-540-70917-6 %B Lecture Notes in Computer Science %N 4393

%0 Journal Article %A Kavitha, Telikepalli %A Mehlhorn, Kurt %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Algorithms to Compute Minimum Cycle Basis in Directed Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1E02-A %F EDOC: 356646 %R 10.1007/s00224-006-1319-6 %F OTHER: Local-ID: C12573CC004A8E26-4000DCDBCE376944C12573E6004AC629-Kavitha2007TCS %7 2007 %D 2007 %* Review method: peer-reviewed %J Theory of Computing Systems %V 40 %N 4 %& 485 %P 485 - 505 %I Springer %C New York, NY %@ false

%0 Journal Article %A Mehlhorn, Kurt %A Michail, Dimitrios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Implementing Minimum Cycle Basis Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1F7F-E %F EDOC: 356694 %R 10.1145/1187436.1216582 %F OTHER: Local-ID: C12573CC004A8E26-7809D4DD4F26C131C125729C0046E9A4-Mehlhorn2007b %7 2007 %D 2007 %X In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G &equals; (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3 &plus; mn2 log n) algorithm. For sparse graphs, this is the currently best-known algorithm. This algorithm's running time can be partitioned into two parts with time O(m3) and O(m2n &plus; mn2 log n), respectively. Our experimental findings imply that for random graphs the true bottleneck of a sophisticated implementation is the O(m2 n &plus; mn2 log n) part. A straightforward implementation would require &#937;(nm) shortest-path computations. Thus, we develop several heuristics in order to get a practical algorithm. Our experiments show that in random graphs our techniques result in a significant speed-up. Based on our experimental observations, we combine the two fundamentally different approaches to compute a minimum cycle basis to obtain a new hybrid algorithm with running time O(m2n2). The hybrid algorithm is very efficient, in practice, for random dense unweighted graphs. Finally, we compare these two algorithms with a number of previous implementations for finding a minimum cycle basis of an undirected graph. %J Journal of Experimental Algorithmics %V 11 %& 2.5.1 %P 2.5.1 - 2-5-14 %I ACM %C New York, N.Y. %@ false

%0 Conference Proceedings %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Minimum Cycle Bases in Graphs Algorithms and Applications : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1FE2-A %F EDOC: 356655 %R 10.1007/978-3-540-74456-6_3 %F OTHER: Local-ID: C12573CC004A8E26-3E9ED811EBD4E1E9C12573FB002FFF04-MehlhornMFCS07 %D 2007 %B Untitled Event %Z date of event: 2007-08-26 - 2007-08-31 %C C&#711; esk&#253; Krumlov, Czech Republic %B Mathematical Foundations of Computer Science 2007 : 32nd International Symposium, MFCS 2007 %E Kucera, Ludek; Kucera, Anton&#237;n %P 13 - 14 %I Springer %@ 3-540-74455-9 %B Lecture Notes in Computer Science %N 4708

%0 Conference Proceedings %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Matchings in Graphs Variations of the Problem : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-1FC9-4 %F EDOC: 356688 %R 10.1007/978-3-540-73556-4_1 %F OTHER: Local-ID: C12573CC004A8E26-8919E7EBB8E64B8EC12573FB00310490-COCOA07 %D 2007 %B Untitled Event %Z date of event: 2007-08-14 - 2007-08-16 %C Xi&#8217;an, China %B Combinatorial Optimization and Applications : First International Conference, COCOA 2007 %E Dress, Andreas; Xu, Yinfeng; Zhu, Binhai %P 1 - 2 %I Springer %@ 3-540-73555-7 %B Lecture Notes in Computer Science %N 4616

%0 Journal Article %A Aronov, Boris %A Asano, Tetsuo %A Katoh, Naoki %A Mehlhorn, Kurt %A Tokuyama, Takeshi %+ 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 Polyline Fitting of Planar Points under Min-sum Criteria : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-23BA-3 %F EDOC: 314580 %F OTHER: Local-ID: C1256428004B93B8-4975B3F8D71B70D6C12571C500423733-mehlhorn06z %D 2006 %* Review method: peer-reviewed %X Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum criteria with respect to L1- and L2 -metrics, which are more appropriate measures than uniform and Hausdorff metrics in statistical context. We present efficient algorithms for the 1-joint versions of the problem and fully polynomial-time approximation schemes for the general k-joint versions. %J International Journal of Computational Geometry and Applications %V 16 %& 97 %P 97 - 116

%0 Journal Article %A Bast, Holger %A Mehlhorn, Kurt %A Sch&#228;fer, Guido %A Tamaki, Hisao %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Matching Algorithms are Fast in Sparse Random Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-2361-9 %F EDOC: 314609 %F OTHER: Local-ID: C1256428004B93B8-257B5C3871441CAAC1256FC0004404AB-BMST05 %D 2006 %* Review method: peer-reviewed %X We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on $n$ vertices, with high probability every non-maximum matching has an augmenting path of length $O(\log n)$. This implies that augmenting path algorithms like the Hopcroft--Karp algorithm for bipartite graphs and the Micali--Vazirani algorithm for general graphs, which have a worst case running time of $O(m\sqrt{n})$, run in time $O(m \log n)$ with high probability, where $m$ is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least $\ln (n)$ [\emph{Average Case Analysis of Algorithms for Matchings and Related Problems}, Journal of the ACM, \textbf{41}(6), 1994]. Our results hold, if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani. %J Theory of Computing Systems %V 39 %& 3 %P 3 - 14 %@ false

%0 Report %A Funke, Stefan %A Klein, Christian %A Mehlhorn, Kurt %A Schmitt, Susanne %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Controlled Perturbation for Delaunay Triangulations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-0027-F72F-3 %Y Algorithms for Complex Shapes with certified topology and numerics %C Instituut voor Wiskunde en Informatica, Groningen, NETHERLANDS %D 2006

%0 Conference Proceedings %A Hariharan, Ramesh %A Telikepalli, Kavitha %A Mehlhorn, Kurt %E Bugliesi, Michele %E Preneel, Bart %E Sassone, Vladimir %E Wegener, Ingo %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-21DE-7 %F EDOC: 314560 %F OTHER: Local-ID: C1256428004B93B8-C5345CC3A9361E5BC12571CA003B984B-HTM06a %D 2006 %B Untitled Event %Z date of event: 2006-07-10 - %C Venice, Italy %X We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is actually a cycle in the underlying undirected graph with edges traversable in both directions. A {&#8211;1,0,1} edge incidence vector is associated with each cycle: edges traversed by the cycle in the right direction get 1 and edges traversed in the opposite direction get -1. The vector space over generated by these vectors is the cycle space of G. A minimum cycle basis is a set of cycles of minimum weight that span the cycle space of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m edges and n vertices runs in time (where &#969;&lt; 2.376 is the exponent of matrix multiplication). Here we present an O(m3n + m2n2logn) algorithm. We also slightly improve the running time of the current fastest randomized algorithm from O(m2nlogn) to O(m2 n + mn2 logn). %B Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I %P 250 - 261 %I Springer %@ 3-540-35904-4 %B Lecture Notes in Computer Science %N 4051

%0 Journal Article %A Irving, Robert W. %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Michail, Dimitrios %A Paluch, Katarzyna %+ 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 Rank-Maximal Matchings : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-23C5-9 %F EDOC: 314364 %F OTHER: Local-ID: C1256428004B93B8-B6D1D2487C87162EC125728E003DA65E-ITMMP2006 %D 2006 %* Review method: peer-reviewed %X Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [2003].We give an algorithm to compute a rank-maximal matching with running time O(min(n + C,C&#8730;n)m), where C is the maximal rank of an edge used in a rank-maximal matching, n is the number of applicants and posts and m is the total size of the preference lists. %J ACM Transactions on Algorithms %V 2 %& 602 %P 602 - 610

%0 Conference Proceedings %A Kettner, Lutz %A Mehlhorn, Kurt %A Pion, Sylvain %A Schirra, Stefan %A Yap, Chee %E Gavrilova, Marina %E Gervasi, Osvaldo %E Kumar, Vipin %E Tan, C. J.Kenneth %E Taniar, David %E Lagan&#224;, Antonio %E Mun, Youngsong %E Choo, Hyunseung %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Reply to "Backward Error Analysis ..." : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-23DB-8 %F EDOC: 314401 %F OTHER: Local-ID: C1256428004B93B8-47155FF99A36D907C12571F1002C58B0-mehlhorn06 %D 2006 %B Untitled Event %Z date of event: 2006-05-08 - %C Glasgow, UK %X The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause implementations to fail. Although this is well known, it is not common knowledge. There is no paper that systematically discusses what can go wrong and provides simple examples for the di.erent ways in which floating-point implementations can fail. Due to this lack of examples, instructors of computational geometry have little material for demonstrating the inadequacy of floating-point arithmetic for geometric computations, students of computational geometry and implementers of geometric algorithms still underestimate the seriousness of the problem, and researchers in our and neighboring disciplines still believe that simple approaches are able to overcome the problem. In this paper, we study simple algorithms for two simple geometric problems, namely computing convex hulls and triangulations of point sets, and show how they can fail and explain why they fail when executed with floating-point arithmetic. %B Computational Science and Its Applications - ICCSA 2006, I %P 60 - 60 %I Springer %@ 3-540-34070-X %B Lecture Notes in Computer Science %N 3980

%0 Journal Article %A Krandick, Werner %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T New bounds for the Descartes method : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-2384-C %F EDOC: 314367 %F OTHER: Local-ID: C1256428004B93B8-8291BD2AF8984049C12571C50041D379-mehlhorn06e %R 10.1016/j.jsc.2005.02.004 %D 2006 %* Review method: peer-reviewed %X We give a new bound for the number of recursive subdivisions in the Descartes <br>method for polynomial real root isolation. Our proof uses Ostrowski&#8217;s theory of <br>normal power series from 1950 which has so far been overlooked in the <br>literature. We combine Ostrowski&#8217;s results with a theorem of Davenport from <br>1985 to obtain our bound. We also characterize normality of cubic polynomials <br>by explicit conditions on their roots and derive a generalization of one of <br>Ostrowski&#8217;s theorems. %J Journal of Symbolic Computation %V 41 %N 1 %& 49 %P 49 - 66

%0 Journal Article %A Kratsch, Dieter %A McConnell, Ross %A Mehlhorn, Kurt %A Spinrad, Jeremy P. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-224D-0 %F EDOC: 314649 %F OTHER: Local-ID: C1256428004B93B8-90DAACD3D4A0C6A8C1256E20004505E1-mehlhorn06b %D 2006 %* Review method: peer-reviewed %X A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs, and for a few other related problems. Previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. We show that our certificates of nonmembership can be authenticated in O(|V|) time. %J SIAM Journal on Computing %V 36 %& 326 %P 326 - 353 %@ false

%0 Conference Proceedings %A Mehlhorn, Kurt %A Osbild, Ralf %A Sagraloff, Michael %E Bugliesi, Michele %E Preneel, Bart %E Sassone, Vladimir %E Wegener, Ingo %+ 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 Reliable and Efficient Computational Geometry Via Controlled Perturbation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-23D5-3 %F EDOC: 314533 %F OTHER: Local-ID: C1256428004B93B8-1C44F76383A124E7C12571CA003ABB0D-MOS06 %D 2006 %B Untitled Event %Z date of event: 2006-07-10 - %C Venice, Italy %X Most algorithms of computational geometry are designed for the Real-RAM and non-degenerate input. We call such algorithms idealistic. Executing an idealistic algorithm with floating point arithmetic may fail. Controlled perturbation replaces an input x by a random nearby in the &#948;-neighborhood of x and then runs the floating point version of the idealistic algorithm on . The hope is that this will produce the correct result for with constant probability provided that &#948; is small and the precision L of the floating point system is large enough. We turn this hope into a theorem for a large class of geometric algorithms and describe a general methodology for deriving a relation between &#948; and L. We exemplify the usefulness of the methodology by examples. Partially supported by the IST Programme of the EU under Contract No IST-006413, Algorithms for Complex Shapes (ACS). %B Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I %P 299 - 310 %I Springer %@ 3-540-35904-4 %B Lecture Notes in Computer Science %N 4051

%0 Conference Proceedings %A Mehlhorn, Kurt %E Calamoneri, Tiziana %E Finocchi, Irene %E Italiano, Giuseppe F. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Reliable and Efficient Geometric Computing : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-23D8-E %F EDOC: 314562 %F OTHER: Local-ID: C1256428004B93B8-EC5B8ABF87E0F995C12571F1002BEFEC-mehlhorn06x %D 2006 %B Untitled Event %Z date of event: 2006-05-29 - %C Rome, Italy %X Reliable implementation of geometric algorithms is a notoriously difficult task. Algorithms are usually designed for the Real-RAM, capable of computing with real numbers in the sense of mathematics, and for non-degenerate inputs. But, real computers are not Real-RAMs and inputs are frequently degenerate. In the first part of the talk we illustrate the pitfalls of geometric computing by way of examples [KMP+04]. The examples demonstrate in a lucid way that standard and frequently taught algorithms can go completely astray when naively implemented with floating point arithmetic. Partially supported by the IST Programme of the EU under Contract No IST-2005-TODO, Algorithms for Complex Shapes (ACS). %B Algorithms and Complexity : 6th Italian Conference, CIAC 2006 %P 1 - 2 %I Springer %@ 3-540-34375-X %B Lecture Notes in Computer Science %N 3998

%0 Journal Article %A Mehlhorn, Kurt %A Michail, Dimitrios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Implementing Minimum Cycle Basis Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-2320-A %F EDOC: 314579 %F OTHER: Local-ID: C1256428004B93B8-6975DD6D0B820206C125728E003E04A2-MM06 %D 2006 %X In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G &equals; (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3 &plus; mn2 log n) algorithm. For sparse graphs, this is the currently best-known algorithm. This algorithm's running time can be partitioned into two parts with time O(m3) and O(m2n &plus; mn2 log n), respectively. Our experimental findings imply that for random graphs the true bottleneck of a sophisticated implementation is the O(m2 n &plus; mn2 log n) part. A straightforward implementation would require &#937;(nm) shortest-path computations. Thus, we develop several heuristics in order to get a practical algorithm. Our experiments show that in random graphs our techniques result in a significant speed-up. Based on our experimental observations, we combine the two fundamentally different approaches to compute a minimum cycle basis to obtain a new hybrid algorithm with running time O(m2n2). The hybrid algorithm is very efficient, in practice, for random dense unweighted graphs. Finally, we compare these two algorithms with a number of previous implementations for finding a minimum cycle basis of an undirected graph. %J ACM Journal of Experimental Algorithmics %V 11 %& 1 %P 1 - 14

%0 Conference Proceedings %A Abraham, David %A Irving, Robert %A Mehlhorn, Kurt %A Kavitha, Telikepalli %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Popular Matchings : %G eng %U http://hdl.handle.net/11858/00-001M-0000-000F-2765-0 %F EDOC: 279204 %D 2005 %B Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2005-01-23 - 2005-01-25 %C Vancouver, Canada %B Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms %P 424 - 432 %I SIAM %@ 0-89871-585-7