7 research outputs found
Engineering Java 7's Dual Pivot Quicksort Using MaLiJan
No full textWild S, Nebel M, Reitzig R, Laube U. Engineering Java 7's Dual Pivot Quicksort Using MaLiJan. In: Proceedings of the 15th Meeting on Algorithm Engineering and Experiments, ALENEX 2013, New Orleans, Louisiana, USA, January 7, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics; 2013: 55--69
Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks
No full textGiven a set of n sticks of various (not necessarily different) lengths, what is the largest length so that we can cut k equally long pieces of this length from the given set of sticks? We analyze the structure of this problem and show that it essentially reduces to a single call of a selection algorithm; we thus obtain an optimal linear-time algorithm. This algorithm also solves the related envy-free stick-division problem, which Segal-Halevi et al. (ACM Trans Algorithms 13(1):1–32, 2016. ISSN: 15496325. https://doi.org/10.1145/2988232) recently used as their central primitive operation for the first discrete and bounded envy-free cake cutting protocol with a proportionality guarantee when pieces can be put to waste
A simple and fast linear-time algorithm for divisor methods of apportionment
No full textAbstractProportional apportionment is the problem of assigning seats to states (resp. parties) according to their relative share of the population (resp. votes), a field heavily influenced by the early work of Michel Balinski, not least his influential 1982 book with Peyton Young (Fair representation, 2nd edn. Brookings Institution Press, Washington, D.C., 2001). In this article, we consider the computational cost of divisor methods (also known as highest averages methods), the de-facto standard solution that is used in many countries. We show that a simple linear-time algorithm can exactly simulate all instances of the family of divisor methods of apportionment by reducing the problem to a single call to a selection algorithm. All previously published solutions were iterative methods that either offer no linear-time guarantee in the worst case or require a complex update step that suffers from numerical instability.</jats:p
A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
No full textProportional apportionment is the problem of assigning seats to parties
according to their relative share of votes. Divisor methods are the de-facto
standard solution, used in many countries.
In recent literature, there are two algorithms that implement divisor
methods: one by Cheng and Eppstein (ISAAC, 2014) has worst-case optimal running
time but is complex, while the other (Pukelsheim, 2014) is relatively simple
and fast in practice but does not offer worst-case guarantees.
We demonstrate that the former algorithm is much slower than the other in
practice and propose a novel algorithm that avoids the shortcomings of both. We
investigate the running-time behavior of the three contenders in order to
determine which is most useful in practice
Collateral damage for R&D manufacturers: how patent sharks operate in markets for technology
No full textPatent sharks, small firms that exploit information asymmetries in markets for technology to gain patent-based competitive advantages, challenge established theory by which (i) markets for technology benefit large firms and (ii) intellectual property rights systems strictly support markets for technology. Empirically linking the sharks' different assault strategies to the patents they deploy, we illustrate that patent sharks will likely be an enduring phenomenon in markets for technology. We discuss policy and strategy implications. Copyright 2010 The Author 2010. Published by Oxford University Press on behalf of Associazione ICC. All rights reserved., Oxford University Press.
Jaguc - a Software package for Environmental Diversity Analyses
No full textNebel M, Wild S, Holzhauser M, et al. Jaguc - a Software package for Environmental Diversity Analyses. J. Bioinformatics and Computational Biology. 2011;9(6):749--773
Bitcoin and the rise of decentralized autonomous organizations
No full textBitcoin represents the first real-world implementation of a “decentralized autonomous organization” (DAO) and offers a new paradigm for organization design. Imagine working for a global business organization whose routine tasks are powered by a software protocol instead of being governed by managers and employees. Task assignments and rewards are randomized by the algorithm. Information is not channeled through a hierarchy but recorded transparently and securely on an immutable public ledger called “blockchain.” Further, the organization decides on design and strategy changes through a democratic voting process involving a previously unseen class of stakeholders called “miners.” Agreements need to be reached at the organizational level for any proposed protocol changes to be approved and activated. How do DAOs solve the universal problem of organizing with such novel solutions? What are the implications? We use Bitcoin as an example to shed light on how a DAO works in the cryptocurrency industry, where it provides a peer-to-peer, decentralized, and disintermediated payment system that can compete against traditional financial institutions. We also invited commentaries from renowned organization scholars to share their views on this intriguing phenomenon.© The Author(s) 201
