139 research outputs found
Comment on: "On the Kung-Traub Conjecture for iterative methods for solving quadratic equations" Algorithms 2016, 9, 1
No full textKung-Traub conjecture states that an iterative method without memory for finding the simple zero of a scalar equation could achieve convergence order 2(d-1), and d is the total number of function evaluations. In an article Babajee, D.K.R. On the Kung-Traub Conjecture for Iterative Methods for Solving Quadratic Equations, Algorithms 2016, 9, 1, doi:10.3390/a9010001, the author has shown that Kung-Traub conjecture is not valid for the quadratic equation and proposed an iterative method for the scalar and vector quadratic equations. In this comment, we have shown that we first reported the aforementioned iterative method.Peer Reviewe
Comment on: "On the Kung-Traub Conjecture for iterative methods for solving quadratic equations" Algorithms 2016, 9, 1
No full textKung-Traub conjecture states that an iterative method without memory for finding the simple zero of a scalar equation could achieve convergence order 2(d-1), and d is the total number of function evaluations. In an article Babajee, D.K.R. On the Kung-Traub Conjecture for Iterative Methods for Solving Quadratic Equations, Algorithms 2016, 9, 1, doi:10.3390/a9010001, the author has shown that Kung-Traub conjecture is not valid for the quadratic equation and proposed an iterative method for the scalar and vector quadratic equations. In this comment, we have shown that we first reported the aforementioned iterative method.Peer ReviewedPostprint (published version
BonnTour: benchmarks & solutions for vehicle routing with time-dependent travel times
No full textThis repository contains the new vehicle routing benchmark instances that we created as part of our work on vehicle routing with time-dependent travel times.
To create this benchmark set, we used map data copyrighted by OpenStreetMap contributors and available from https://www.openstreetmap.org under the Open Database License (ODbL) v1.0, and speed data retrieved from Uber Movement, (c) 2022 Uber Technologies, Inc., https://movement.uber.com, under a Creative Commons Attribution Non-Commercial license.
The solutions reported in the related publication
Jannis Blauth, Stephan Held, Dirk Müller, Niklas Schlomberg, Vera Traub, Thorben Tröbst, Jens Vygen:
Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks.
Discrete Optimization, Volume 53, 2024, 100848.
are also contained.
This repository is a snapshot of https://gitlab.com/muelleratorunibonnde/vrptdt-benchmark (git revision: 1306f4b22a5ecf3307ed), i.e. the version that was used in the above publication
Pictorial Interview of Children’s Metacognition and Executive Functions (PIC–ME): A Comparison Between Children With and Without Attention Deficit Hyperactivity Disorder
No full textAbstract
Date Presented 3/30/2017
The Pictorial Interview of Children’s Metacognition and Executive Functions (PIC–ME) was designed to evaluate self-perception of executive function challenges in daily life among children with attention deficit hyperactivity disorder and to promote their engagement in goal setting. Results support the initial reliability and validity of the PIC–ME.
Primary Author and Speaker: Ruthie Traub Bar-Ilan
Contributing Authors: Adina Maeir</jats:p
What was liberalism? the past, present, and promise of a noble idea
No full text"In the vertiginous era of Trump and Marine le Pen, liberalism's status is challenged. There is a widespread fear that liberal values, long taken for granted, are now in danger -- not only from authoritarian countries abroad, but also from a loss of faith inside the liberal world. What happened? Why did liberalism lose the majority support it once enjoyed? And what is so precious about liberalism in the first place? In What Was Liberalism?, award-winning journalist and author James Traub tackles these questions by examining the history of liberalism, from the American and French revolutions through the writings of John Stuart Mill and early-twentieth-century American progressives to liberalism's midcentury triumph in the West, its shaky present, and its uncertain future. Liberalism, Traub shows, began with a commitment to individual liberty, but it didn't end there. Over time, liberals sought to balance freedom of speech and action with goods like justice and equality, opposing both economic exploitation and totalitarianism. Partly as a result, the relationship between liberalism and democracy also evolved. Many nineteenth-century liberals were deeply worried about the democracy's illiberal effects, but by the middle of the twentieth century, liberalism had become the consensus faith of a wide swath of Americans and Europeans, both left and right. Yet even as the liberal West emerged victorious from the Cold War, liberalism's broad majoritarian foundations were crumbling, falling prey to accelerating economic inequality and the vexing challenges of race and immigration. Traub explores how liberalism burned out of sight like an underground fire, and how it exploded into view in Europe and the United States in recent decades.
Vehicle Routing in Theory and Practice
No full textIn this thesis, we study combinatorial optimization problems that arise in logistics and can be summarized under the name vehicle routing. We tackle these problems from two different points of view. First, we study their computational complexity. All problems we look at are generalizations of the famous traveling salesperson problem, TSP for short: a driver needs to visit certain customers (e.g., to deliver goods) and return to the starting point at the end of the tour. The goal is to compute a tour of minimum length (or cost). We provide improved approximation guarantees for two well-known natural generalizations of this problem. Both variants are of high relevance in logistics. In the first variant, known as the prize-collecting TSP, we are allowed to reject customer requests, which comes at customer-specific penalties. The goal is then to optimize the sum of tour length and total penalty for rejected inquiries. We improve the best known approximation ratio of roughly 1.914 (due to Goemans) to 1.599, which significantly reduces the gap between the approximability of the TSP and its prize-collecting variant. The second variant of the TSP for which we provide improved approximation guarantees is the capacitated vehicle routing problem. In many applications, the goods that need to be delivered to customers exceed the capacity of a single vehicle. Hence, we need to distribute the goods to several vehicles and compute an efficient route for each of these such that the sum of tour lengths is minimized. We improve and simplify an approach that was initiated in my master’s thesis, which led to the first improvement of the approximation ratio of the classical tour partitioning approach. We obtain a better approximation ratio for several major variants of the problem. Second, we study vehicle routing problems from a practical point of view. On typical real-world instances, the approximation algorithms discussed in the first part of this thesis are not practical, neither in terms of solution quality nor in terms of running time. Moreover, we need to satisfy various additional constraints such as time windows, working time limits, and limited heterogeneous vehicle fleets. We present an algorithm called BonnTour that covers a wide class of vehicle routing problems and provides high-quality solutions in reasonable computation time. On numerous benchmarks, the cost of the computed solution comes close to the optimum or the best known. On some benchmark instances, we present new best known solutions. Our algorithm takes into account time-dependent travel time fluctuations that are caused by congestion, which leads to much more reliable tour plans. We provide a new set of realistic and large-scale benchmark instances for vehicle routing with time-dependent travel times to foster future research on this problem. BonnTour is developed in cooperation with our industry partner Greenplan, and is used on a daily basis to solve real-world vehicle routing problems for various companies
Improved Approximation Algorithms for Weighted <em>k</em>-Set Packing
No full textWe study the weighted k-Set Packing problem, which is defined as follows: The input consists of a finite collection S of non-empty sets, each of cardinality at most k, as well as a positive weight for each of the sets. The task is to compute a subcollection A of S such that the sets in A are pairwise disjoint and the total weight of A is maximum.
For k=1 and k=2, the weighted k-Set Packing problem can be solved in polynomial time. In contrast, if k is at least 3, even the special case where all weights are equal to 1, the unweighted k-Set Packing problem, is NP-hard.
In this thesis, we study polynomial-time approximation algorithms for (variants of) the weighted k-Set Packing problem for k greater or equal to 3. The technique that has proven most successful in designing these algorithms is local search.
The state-of-the-art algorithms for the unweighted case are due to Cygan and Fürer and Yu . They use well-structured local improvements of up to logarithmic size and attain approximation ratios of (k+1+epsilon)/3. For general weights, only local improvements of constant size have been studied prior to the results presented in this thesis. Berman has devised a (k+1+epsilon)/2-approximation algorithm. By considering a broader class of local improvements of constant size, I obtained an improved guarantee of (k+1+epsilon)/2-1/63,700,992 in the course of my Master's thesis.
In this PhD thesis, we first show that a much smaller class of local improvements than in our previous work suffices to obtain an approximation ratio of (k+1)/2-1/1000. Next, we address the question which approximation guarantees can be achieved for the weighted k-Set Packing problem via local improvements of logarithmically bounded size, and provide an asymptotically tight answer. We obtain approximation guarantees of (k+1+lambda_k)/2, where lambda_k converges to 1 as k approaches infinity. Moreover, we establish a lower bound of k/2
By applying a black box algorithm for the unweighted k-Set Packing problem to generate candidate local improvements of potentially super-logarithmic size, we manage to breach the k/2 barrier and obtain approximation guarantees of 0.4999*k + 0.501 for the weighted k-Set Packing problem. We further leverage the above approach to establish a general link between approximation guarantees achievable for the unweighted and the weighted k-Set Packing problem.
Finally, we provide a 4/3-approximation for the hereditary 2-3-Set Packing problem, a special case of weighted 3-Set Packing. Using a reduction by Fernandes and Lintzmayer, this further implies a 4/3-approximation for the Maximum Leaf Spanning Arborescence problem in acyclic digraphs. Our result improves upon the previously best known guarantee of 7/5 for both problems
Improving on Best-of-Many-Christofides for T-tours
No full textISSN:0167-6377ISSN:1872-7468ISSN:1872-746
Approximation Algorithms for Traveling Salesman Problems
No full textThe traveling salesman problem is the probably most famous problem in combinatorial optimization. Given a graph G and nonnegative edge costs, we want to find a closed walk in G that visits every vertex at least once and has minimum cost. We consider both the symmetric traveling salesman problem (TSP) where G is an undirected graph and the asymmetric traveling salesman problem (ATSP) where G is a directed graph. We also investigate the unit-weight special cases and the more general path versions, where we do not require the walk to be closed, but to start and end in prescribed vertices s and t. In this thesis we give improved approximation algorithms and better upper bounds on the integrality ratio of the classical linear programming relaxations for several of these traveling salesman problems. For this we use techniques arising from various parts of combinatorial optimization such as linear programming, network flows, ear-decompositions, matroids, and T-joins. Our results include a (22 + &epsilon)-approximation algorithm for ATSP (for any &epsilon > 0), the first constant upper bound on the integrality ratio for s-t-path ATSP, a new upper bound on the integrality ratio for s-t-path TSP, and a black-box reduction from s-t-path TSP to TSP
- …
