1,625 research outputs found
Brief Announcement: Distinct Gathering Under Round Robin
Full text linkWe resolve one of the longest-standing questions about autonomous mobile robots in a surprising way.
Distinct Gathering is the fundamental cooperation task of letting robots, initially scattered across the plane in distinct locations, gather in an arbitrary single point. The scheduler Round Robin cyclically activates the robots one by one in a fixed order. When activated, a robot perceives all robot locations and moves wherever it wants based only on this information. For n = 2 robots, the task is trivial. What happens for n ≥ 3 has remained an open problem for decades by now. The established conjecture declares the task to be impossible in this case. We prove that it is indeed impossible for n = 3 but, to great surprise, possible again for any n ≥ 4. We go beyond the standard requirements by providing a very robust algorithm that does not require any consistency or self-consistency for the local Cartesian maps perceived by the robots and works even for non-rigid movement, that is, if robots may be unpredictably stopped and deactivated during a movement
Efficient Circuit Simulation in MapReduce
Full text linkThe MapReduce framework has firmly established itself as one of the most widely used parallel computing platforms for processing big data on tera- and peta-byte scale. Approaching it from a theoretical standpoint has proved to be notoriously difficult, however. In continuation of Goodrich et al.’s early efforts, explicitly espousing the goal of putting the MapReduce framework on footing equal to that of long-established models such as the PRAM, we investigate the obvious complexity question of how the computational power of MapReduce algorithms compares to that of combinational Boolean circuits commonly used for parallel computations. Relying on the standard MapReduce model introduced by Karloff et al. a decade ago, we develop an intricate simulation technique to show that any problem in NC (i.e., a problem solved by a logspace-uniform family of Boolean circuits of polynomial size and a depth polylogarithmic in the input size) can be solved by a MapReduce computation in O(T(n)/log n) rounds, where n is the input size and T(n) is the depth of the witnessing circuit family. Thus, we are able to closely relate the standard, uniform NC hierarchy modeling parallel computations to the deterministic MapReduce hierarchy DMRC by proving that NC^{i+1} subseteq DMRC^i for all i in N. Besides the theoretical significance, this result has important applied aspects as well. In particular, we show for all problems in NC^1 - many practically relevant ones, such as integer multiplication and division and the parity function, being among these - how to solve them in a constant number of deterministic MapReduce rounds
Removable Online Knapsack and Advice
Full text linkIn the proportional knapsack problem, we are given a knapsack of some capacity and a set of variably sized items. The goal is to pack a selection of these items that fills the knapsack as much as possible. The online version of this problem reveals the items and their sizes not all at once but one by one. For each item, the algorithm has to decide immediately whether to pack it or not. We consider a natural variant of this online knapsack problem, which has been coined removable knapsack. It differs from the classical variant by allowing the removal of any packed item from the knapsack. Repacking is impossible, however: Once an item is removed, it is gone for good.
We analyze the advice complexity of this problem. It measures how many advice bits an omniscient oracle needs to provide for an online algorithm to reach any given competitive ratio, which is - understood in its strict sense - just the algorithm’s approximation factor. The online knapsack problem is known for its peculiar advice behavior involving three jumps in competitivity. We show that the advice complexity of the version with removability is quite different but just as interesting: The competitivity starts from the golden ratio when no advice is given. It then drops down to 1+ε for a constant amount of advice already, which requires logarithmic advice in the classical version. Removability comes as no relief to the perfectionist, however: Optimality still requires linear advice as before. These results are particularly noteworthy from a structural viewpoint for the exceptionally slow transition from near-optimality to optimality.
Our most important and demanding result shows that the general knapsack problem, which allows an item’s value to differ from its size, exhibits a similar behavior for removability, but with an even more pronounced jump from an unbounded competitive ratio to near-optimality within just constantly many advice bits. This is a unique behavior among the problems considered in the literature so far.
An advice analysis is interesting in its own right, as it allows us to measure the information content of a problem and leads to structural insights. But it also provides insurmountable lower bounds, applicable to any kind of additional information about the instances, including predictions provided by machine-learning algorithms and artificial intelligence. Unexpectedly, advice algorithms are useful in various real-life situations, too. For example, they provide smart strategies for cooperation in winner-take-all competitions, where several participants pool together to implement different strategies and share the obtained prize. Further illustrating the versatility of our advice-complexity bounds, our results automatically improve some of the best known lower bounds on the competitive ratio for removable knapsack with randomization. The presented advice algorithms also automatically yield deterministic algorithms for established deterministic models such as knapsack with a resource buffer and various problems with more than one knapsack. In their seminal paper introducing removability to the knapsack problem, Iwama and Taketomi have indeed proposed a multiple knapsack problem for which we can establish a one-to-one correspondence with the advice model; this paper therefore even provides a comprehensive analysis for this up until now neglected problem
Correction: Dermal Exposure Assessment to Pesticides in Farming Systems in Developing Countries: Comparison of Models. Int. J. Environ. Res. Public Health 2015, 12, 4670–4696
No full textWe wish to make the following changes to the published article [1], agreed upon by all authors. Claudia R. Binder has withdrawn her co-authorship. The corrected author list should therefore read: Camilo Lesmes-Fabian.[...
An Open Pouring Problem
Full text linkWe analyze a little riddle that has challenged mathematicians for half a century.
Imagine three clubs catering to people with some niche interest. Everyone willing to join a club has done so and nobody new will pick up this eccentric hobby for the foreseeable future, thus the mutually exclusive clubs compete for a common constituency. Members are highly invested in their chosen club; only a targeted campaign plus prolonged personal persuasion can convince them to consider switching. Even then, they will never be enticed into a bigger group as they naturally pride themselves in avoiding the mainstream. Therefore each club occasionally starts a campaign against a larger competitor and sends its own members out on a recommendation program. Each will win one person over; the small club can thus effectively double its own numbers at the larger one’s expense.
Is there always a risk for one club to wind up with zero members, forcing it out of business? If so, how many campaign cycles will this take
Complexity of Stability
Full text linkGraph parameters such as the clique number, the chromatic number, and the independence number are central in many areas, ranging from computer networks to linguistics to computational neuroscience to social networks. In particular, the chromatic number of a graph (i.e., the smallest number of colors needed to color all vertices such that no two adjacent vertices are of the same color) can be applied in solving practical tasks as diverse as pattern matching, scheduling jobs to machines, allocating registers in compiler optimization, and even solving Sudoku puzzles. Typically, however, the underlying graphs are subject to (often minor) changes. To make these applications of graph parameters robust, it is important to know which graphs are stable for them in the sense that adding or deleting single edges or vertices does not change them. We initiate the study of stability of graphs for such parameters in terms of their computational complexity. We show that, for various central graph parameters, the problem of determining whether or not a given graph is stable is complete for Θ₂ᵖ, a well-known complexity class in the second level of the polynomial hierarchy, which is also known as "parallel access to NP.
Die Ringer-Kunst des Fabian von Auerswald /
No full textIn portfolio."Gedruckt zu Wittemberg durch Hans Lufft. M.D.XXXIX."--Colophon.85 full-page woodcuts by Lucas Cranach the Younger, representing the author in his 85 wrestling positions.Facsimile of the edition of 1539 with title: Ringen Kunst: fünff und achtzig Stücke, zu Ehren Kurfürstlichen Gnaden zu Sachsen [etc.] Durch Fabian von Auerswald zugericht.Mode of access: Internet
Content-Oblivious Leader Election on Rings
Full text linkIn content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation.
Our goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity O(n ⋅ ID_max), where ID_max is the maximal assigned ID. As it turns out, this dependency on ID_max is inherent: we show a lower bound of Ω(n log(ID_max/n)) messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings, where nodes cannot tell which channel leads to which neighbor. In this case, however, the algorithm does not terminate but only reaches quiescence
Finding Optimal Solutions With Neighborly Help
Full text linkCan we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems; most notably graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted).
We focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level.
Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For Vertex Cover, we show that recognizing beta-vertex-critical graphs is complete for Theta_2^p (parallel access to NP), obtaining the first completeness result for a criticality problem for this class
Fabian lernt "schwimmen"
No full textMit der Absicht, eine Brücke zwischen deutschsprachiger Literatur und Humanistischer Psychologie zu konstruieren, geht die vorliegende Arbeit der Frage nach, ob es möglich ist, eine fiktive Person, die vor dem Hintergrund der Weltwirtschaftskrise von 1929 im Verlauf einer Romanhandlung arbeitslos geworden ist, durch Anwendung einer humanistischen Therapieform wieder in die Arbeitswelt zu integrieren. Die fiktive Person ist Jakob Fabian aus Erich Kästners neusachlichem Zeitroman Fabian. Die Geschichte eines Moralisten, erschienen 1931, und bei der humanistischen Therapieform handelt es sich um den „Klientenzentrierten Ansatz“ nach Carl Rogers. Die zentrale Forschungsfrage wird in zwei großen Schritten beantwortet: Im ersten Schritt werden themenrelevante Aspekte hinsichtlich Roman, Autor sowie Protagonist erläutert und analysiert, bis die Romanfigur Jakob Fabian zum Klienten Jakob Fabian wird und ein Anamnesebericht über diesen vorliegt. Basierend darauf, werden mit dem Ergebnis der beruflichen Rehabilitation im zweiten Schritt klientenzentriert-orientierte Therapiegespräche in einem realen Setting durchgeführt und transkribiert. Das Konzept dieser Arbeit kann als Modell auf weitere Arbeitslosenromane der Weimarer Republik angewendet werden. Zusätzlich besteht auch die Möglichkeit, das Setting an Beratungssituationen anzupassen.With the intention of constructing a bridge between German literature and “Humanistic Psychology”, the present thesis analyses the question, whether it is possible to reintegrate a fictitious man into the working environment by applying a humanistic type of therapy, who, against the background of the world economic crisis of 1929, in the course of a novel's plot has lost his job. Jakob Fabian is the fictional character in Erich Kästner’s new objectivity period novel Fabian. The story of a moralist, pub-lished in 1931, and the humanistic therapeutic method is the Rogerian Client-centered approach. The core issue is answered in two major steps: In the first step, issue-specific aspects regarding novel, author and protagonist are explained and analysed until the fictional character Jakob Fabian turns into the client Jakob Fabian and until an anamnesis report is available. Based on this, with the outcome of vocational rehabilitation in the second step, client-centred-oriented therapy sessions are conducted in a real setting and transcribed. The concept of this work can also be used as a model for other novels about unemployment during the Weimar Republic. In addition, it is also possible to adjust the setting of advisory situations
- …
