1,720,952 research outputs found
Het Cap Set-probleem
No full textMei vorig jaar zorgde de Nederlandse wiskundige Dion Gijswijt van de TU Delft samen met Jordan Ellenberg (University of Wisconsin) voor een doorbraak in het Cap Set-probleem. In dit artikel bespreken Aart Blokhuis en Dion Gijswijt het probleem en de gevonden oplossing aan de hand van het kaartspel SETDiscrete Mathematics and Optimizatio
Using the slice rank for finding upper bounds on the size of cap sets
No full textThe cap set problem consists of finding the maximum size cap sets, i.e. sets without a 3-term arithmetic progression in F₃. In this thesis several known results on the behavior of this number as n → ∞ are presented. In particular we discuss a reformulation by Terence Tao and Will Sawin of a proof found by Dion Gijswijt and Jordan Ellenberg. It uses the slice rank, a rank that is defined for elements of tensor products, to give upper bounds on the size of the cap sets. In this report we will explain the slice rank and how it is related to the size of cap sets. We will also explore whether the slice rank might be used for bounding the size of arithmetic progression-free sets in F_q for q ≠ 3. We show that we can not use the slice rank to give a non-trivial upper bound on the size of n-term progression-free sets for n ≥ 7. This was already known for n ≥ 8
Constructing tree decompositions of graphs with bounded gonality
No full textIn this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.Accepted author manuscriptDiscrete Mathematics and Optimizatio
On the Sybil-Proofness of Accounting Mechanisms in P2P Networks
No full textOnline P2P file sharing networks rely on the cooperation of participants to function effectively. Agents upand download files to one another without the need for any central authority. If agents all contribute to the network and share roughly the same amounts of data as they contribute the network will operate, however if some agents decide to defect and consume far more resources than they contribute the file sharing will stagnate. In online networks with some kind of central authority, such as Ebay, Airbnb, etc. cooperation is achieved through a review system, which is maintained and secured by the central authority. P2P networks are however distributed and cooperation must be achieved without this central mitigator. One way of approaching this problem is by observing cooperative biological communities in nature. One finds that cooperation among biological organisms is achieved through a mechanism called indirect reciprocity. Indirect reciprocity is based on a reputation scheme in which agents share information about each other’s cooperativeness aiding one another in deciding who to interact with and who to shun. In this work we analyse properties a reputation mechanism must satisfy in order to achieve cooperation in P2P networks, incentivising contributions and penalising excessive comsumption of data. In particular, we determine under what conditions reputation mechanisms are resistant to attacks on the P2P network. We focus on one attack above all, namely that of a sybil attack in which a malicious agent creates multiple fake identities who report high levels of cooperativeness about one another. We determine properties accounting mechanisms must satisfy in order to prevent attackers from obtaining arbitrarily high reputation and to consequently be able to consume arbitrarily large amounts of data. This thesis offers a theoretical framework for evaluating the effectiveness of reputation mechanisms on the basis of their ability to induce cooperation and their resistance to sybil attacks.Applied Mathematic
Integer packing sets form a well-quasi-ordering
No full textAn integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y≤x is in the set as well. The main result of this paper is that integer packing sets, ordered by inclusion, form a well-quasi-ordering. This result allows us to answer a recently posed question: the k-aggregation closure of any packing polyhedron is again a packing polyhedron.Accepted Author ManuscriptDiscrete Mathematics and Optimizatio
De partitiefunctie van Rademacher
No full textThere are several ways to write the number 5 as a sum of positive integers, disregarding order. A quick calculation shows that this can be done in 7 ways: 5 = 5, 5 = 4 + 1, 5 = 3 + 2, 5 = 3 + 1 + 1, 5 = 2 + 2 + 1, 5 = 2 + 1 + 1 + 1 and 5 = 1 + 1 + 1 + 1 + 1. In the same way, we can count the number of ways for each integer n. Although this calculation is trivial, a closed form for this function is not as easily obtained as one for combinations, for example. This work formulates and proves Rademacher's formula for these partition numbers. It also tries to uncover some key ideas behind the proof, the supporting theory and other inspirations
The impact on the final delivery schedule of different procedures that handle arriving customers during route optimization in a real-time Dynamic Time Slot Management system
No full textDynamic Time Slot Management (DTSM) is a system often used in online retail to manage the delivery of goods to customers. With DTSM customers arrive over time and place orders. They get presented with a set of time slots and the customer picks the time slot in which he wants the goods to be delivered to his home. A DTSM system creates a time slot offer for the customers based on the current delivery schedule, which is a solution to a Vehicle Routing Problem (VRP). Each accepted customer is added to this delivery schedule. This delivery schedule gets periodically optimized by an optimization algorithm. During this optimization, new customers may arrive and receive time slots based on the non-optimized schedule, which causes a discontinuity in the system. In this thesis, five different procedures have been created that deal with this problem. The impact of the different procedures is analyzed by simulating the DTSM system and comparing the final delivery schedules. Solving the problem by leaving out the optimization or insertion step of the DTSM system is outperformed by all procedures. Procedures that barely make use of the optimized schedule accept the least number of customers. The procedure that delays customers, which makes it similar to the theoretical setting, accepts the most customers, but this comes at the cost of poor customer service. The most promising results are found by the procedure that inserts new customers into the optimized schedule. Enhancing this procedure with a merge algorithm improves the performance slightly.Applied Mathematic
The impact of soft time windows with penalties on the objective values of large real-world Vehicle Routing Problems
No full textIn a Vehicle Routing Problem with Time Windows (VRPTW), orders have to be picked up and delivered within certain time windows. In practice, planners often allow violations of these time windows, when the solutions with violations have better objective values. This is done by changing the problem into a Vehicle Routing Problem with Soft Time Windows (VRPSTW). In this thesis, the effect of soft time windows on the objective values of a real-world VRP is analysed for multiple single-day cases of a distribution company. The used algorithm is a heuristic, based on local search methods. At first, a sensitivity analysis is performed on the sensitivity of the number of planned tasks to the time window tolerance. The addition of time window tolerance increases the number of planned tasks in most of the cases. Furthermore, when the tolerance increases, the number of planned tasks generally increases as well, until the number of planned tasks is equal to the number of tasks that is planned when the time windows are completely removed. In the second part of the experiments, trade-offs between the cost function and the amount of violation are investigated, by varying the slope of the linear penalty function (for a fixed tolerance). In general, a higher penalty leads to a lower amount of violation and a higher cost (without penalties), but this is not a monotone correlation. For the smaller cases, the costs can be lowered by 4.8% to 9.0%. To reach this minimum cost, an average violation of 1 to 7 minutes per task has to be accepted. For the bigger cases, only the lowest penalty values lead to a cost improvement. Here, the lowest cost value is achieved by choosing the zero function as the penalty function, which means that the corresponding solution contains a large amount of violation.Applied Mathematic
On The Cap Set Problem: upper bounds on maximal cardinalities of caps in dimensions seven to ten
No full textThis thesis concerns the cap set problem in affine geometry. The problem is illustrated by the card game SET and its geometrical interpretation in ternary affine space. The maximal cardinality of a cap is known for the dimension one to six. For the four lowest dimensions, a maximal cap is constructed and the optimality of its size proven. From there, two recursive methods are described and applied to obtain upper bounds for the maximal size of caps in dimensions seven to ten. The best found upper bounds are 291, 771, 2070 and 5619, respectively
- …
