Zero-sum problems in finite cyclic groups

The purpose of this thesis is to investigate some open problems in the area of combinatorial number theory referred to as zero-sum theory. A zero-sequence in a finite cyclic group G is said to have the basic property if it is equivalent under group automorphism to one which has sum precisely IGI when this sum is viewed as an integer. This thesis investigates two major problems, the first of which is referred to as the basic pair problem. This problem seeks to determine conditions for which every zero-sequence of a given length in a finite abelian group has the basic property. We resolve an open problem regarding basic pairs in cyclic groups by demonstrating that every sequence of length four in Zp has the basic property, and we conjecture on the complete solution of this problem. The second problem is a 1988 conjecture of Kleitman and Lemke, part of which claims that every sequence of length n in Zn has a subsequence with the basic property. If one considers the special case where n is an odd integer we believe this conjecture to hold true. We verify this is the case for all prime integers less than 40, and all odd integers less than 26. In addition, we resolve the Kleitman-Lemke conjecture for general n in the negative. That is, we demonstrate a sequence in any finite abelian group isomorphic to Z2p (for p ~ 11 a prime) containing no subsequence with the basic property. These results, as well as the results found along the way, contribute to many other problems in zero-sum theory.

The dynamics of a genetic algorithm under stabilizing selection

A formalism recently introduced by Prugel-Bennett and Shapiro uses the methods of statistical mechanics to model the dynamics of genetic algorithms. To be of more general interest than the test cases they consider. In this paper, the technique is applied to the subset sum problem, which is a combinatorial optimization problem with a strongly non-linear energy (fitness) function and many local minima under single spin flip dynamics. It is a problem which exhibits an interesting dynamics, reminiscent of stabilizing selection in population biology. The dynamics are solved under certain simplifying assumptions and are reduced to a set of difference equations for a small number of relevant quantities. The quantities used are the population's cumulants, which describe its shape, and the mean correlation within the population, which measures the microscopic similarity of population members. Including the mean correlation allows a better description of the population than the cumulants alone would provide and represents a new and important extension of the technique. The formalism includes finite population effects and describes problems of realistic size. The theory is shown to agree closely to simulations of a real genetic algorithm and the mean best energy is accurately predicted.

On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

Knapsack sets for cryptography

The basic goal of this study is to extend old and propose new ways to generate knapsack sets suitable for use in public key cryptography. The knapsack problem and its cryptographic use are reviewed in the introductory chapter. Terminology is based on common cryptographic vocabulary. For example, solving the knapsack problem (which is here a subset sum problem) is termed decipherment. Chapter 1 also reviews the most famous knapsack cryptosystem, the Merkle Hellman system. It is based on a superincreasing knapsack and uses modular multiplication as a trapdoor transformation. The insecurity caused by these two properties exemplifies the two general categories of attacks against knapsack systems. These categories provide the motivation for Chapters 2 and 4. Chapter 2 discusses the density of a knapsack and the dangers of having a low density. Chapter 3 interrupts for a while the more abstract treatment by showing examples of small injective knapsacks and extrapolating conjectures on some characteristics of knapsacks of larger size, especially their density and number. The most common trapdoor technique, modular multiplication, is likely to cause insecurity, but as argued in Chapter 4, it is difficult to find any other simple trapdoor techniques. This discussion also provides a basis for the introduction of various categories of non injectivity in Chapter 5. Besides general ideas of non injectivity of knapsack systems, Chapter 5 introduces and evaluates several ways to construct such systems, most notably the "exceptional blocks" in superincreasing knapsacks and the usage of "too small" a modulus in the modular multiplication as a trapdoor technique. The author believes that non injectivity is the most promising direction for development of knapsack cryptosystema. Chapter 6 modifies two well known knapsack schemes, the Merkle Hellman multiplicative trapdoor knapsack and the Graham Shamir knapsack. The main interest is in aspects other than non injectivity, although that is also exploited. In the end of the chapter, constructions proposed by Desmedt et. al. are presented to serve as a comparison for the developments of the subsequent three chapters. Chapter 7 provides a general framework for the iterative construction of injective knapsacks from smaller knapsacks, together with a simple example, the "three elements" system. In Chapters 8 and 9 the general framework is put into practice in two different ways. Modularly injective small knapsacks are used in Chapter 9 to construct a large knapsack, which is called the congruential knapsack. The addends of a subset sum can be found by decrementing the sum iteratively by using each of the small knapsacks and their moduli in turn. The construction is also generalized to the non injective case, which can lead to especially good results in the density, without complicating the deciphering process too much. Chapter 9 presents three related ways to realize the general framework of Chapter 7. The main idea is to join iteratively small knapsacks, each element of which would satisfy the superincreasing condition. As a whole, none of these systems need become superincreasing, though the development of density is not better than that. The new knapsack systems are injective but they can be deciphered with the same searching method as the non injective knapsacks with the "exceptional blocks" in Chapter 5. The final Chapter 10 first reviews the Chor Rivest knapsack system, which has withstood all cryptanalytic attacks. A couple of modifications to the use of this system are presented in order to further increase the security or make the construction easier. The latter goal is attempted by reducing the size of the Chor Rivest knapsack embedded in the modified system. '

Extremal problems on sum-free sets and coverings in tridimensional spaces

Given a prime power q, define c (q) as the minimum cardinality of a subset H of F 3 q which satisfies the following property: every vector in this space di ff ers in at most 1 coordinate from a multiple of a vector in H. In this work, we introduce two extremal problems in combinatorial number theory aiming to discuss a known connection between the corresponding coverings and sum-free sets. Also, we provide several bounds on these maps which yield new classes of coverings, improving the previous upper bound on c (q)

Decentralized supply chain formation using max-sum loopy belief propagation

Supply chain formation is the process by which a set of producers within a network determine the subset of these producers able to form a chain to supply goods to one or more consumers at the lowest cost. This problem has been tackled in a number of ways, including auctions, negotiations, and argumentation-based approaches. In this paper we show how this problem can be cast as an optimization of a pairwise cost function. Optimizing this class of energy functions is NP-hard but efficient approximations to the global minimum can be obtained using loopy belief propagation (LBP). Here we detail a max-sum LBP-based approach to the supply chain formation problem, involving decentralized message-passing between supply chain participants. Our approach is evaluated against a well-known decentralized double-auction method and an optimal centralized technique, showing several improvements on the auction method: it obtains better solutions for most network instances which allow for competitive equilibrium (Competitive equilibrium in Walsh and Wellman is a set of producer costs which permits a Pareto optimal state in which agents in the allocation receive non-negative surplus and agents not in the allocation would acquire non-positive surplus by participating in the supply chain) while also optimally solving problems where no competitive equilibrium exists, for which the double-auction method frequently produces inefficient solutions. © 2012 Wiley Periodicals, Inc.

Vehicle routing and location routing problems with minimum latency: algorithms and models

Latency can be defined as the sum of the arrival times at the customers. Minimum latency problems are specially relevant in applications related to humanitarian logistics. This thesis presents algorithms for solving a family of vehicle routing problems with minimum latency. First the latency location routing problem (LLRP) is considered. It consists of determining the subset of depots to be opened, and the routes that a set of homogeneous capacitated vehicles must perform in order to visit a set of customers such that the sum of the demands of the customers assigned to each vehicle does not exceed the capacity of the vehicle. For solving this problem three metaheuristic algorithms combining simulated annealing and variable neighborhood descent, and an iterated local search (ILS) algorithm, are proposed. Furthermore, the multi-depot cumulative capacitated vehicle routing problem (MDCCVRP) and the multi-depot k-traveling repairman problem (MDk-TRP) are solved with the proposed ILS algorithm. The MDCCVRP is a special case of the LLRP in which all the depots can be opened, and the MDk-TRP is a special case of the MDCCVRP in which the capacity constraints are relaxed. Finally, a LLRP with stochastic travel times is studied. A two-stage stochastic programming model and a variable neighborhood search algorithm are proposed for solving the problem. Furthermore a sampling method is developed for tackling instances with an infinite number of scenarios. Extensive computational experiments show that the proposed methods are effective for solving the problems under study.

Implicit vector equilibrium problems with applications

Let X and Y be Hausdorff topological vector spaces, K a nonempty, closed, and convex subset of X, C: K--> 2(Y) a point-to-set mapping such that for any x is an element of K, C(x) is a pointed, closed, and convex cone in Y and int C(x) not equal 0. Given a mapping g : K --> K and a vector valued bifunction f : K x K - Y, we consider the implicit vector equilibrium problem (IVEP) of finding x* is an element of K such that f (g(x*), y) is not an element of - int C(x) for all y is an element of K. This problem generalizes the (scalar) implicit equilibrium problem and implicit variational inequality problem. We propose the dual of the implicit vector equilibrium problem (DIVEP) and establish the equivalence between (IVEP) and (DIVEP) under certain assumptions. Also, we give characterizations of the set of solutions for (IVP) in case of nonmonotonicity, weak C-pseudomonotonicity, C-pseudomonotonicity, and strict C-pseudomonotonicity, respectively. Under these assumptions, we conclude that the sets of solutions are nonempty, closed, and convex. Finally, we give some applications of (IVEP) to vector variational inequality problems and vector optimization problems. (C) 2003 Elsevier Science Ltd. All rights reserved.

Who Matters in Coordination Problems?

We consider a common investment project that is vulnerable to a self-ful lling coordination failure and hence is strategically risky. Based on their private information, agents - who have heterogeneous investment incentives - form expectations or 'sentiments' about the project's outcome. We find that the sum of these sentiments is constant across di erent strategy profiles and it is independent of the distribution of incentives. As a result, we can think of sentiment as a scarce resource divided up among the di erent payo types. Applying this nding, we show that agents who bene t little from the project's success have a large impact on the coordination process. The agents with small bene ts invest only if their sentiment towards the project is large per unit investment cost. As the average sentiment is constant, a subsidy decreasing the investment costs of these agents will \free up" a large amount of sentiment, provoking a large impact on the whole economy. Intuitively, these agents, insensitive to the project's outcome and hence to the actions of others, are in uential because they modify their equilibrium behavior only if the others change theirs substantially.

Efficient Algorithms for Coastal Geographic Problems

The increasing performance of computers has made it possible to solve algorithmically problems for which manual and possibly inaccurate methods have been previously used. Nevertheless, one must still pay attention to the performance of an algorithm if huge datasets are used or if the problem iscomputationally difficult. Two geographic problems are studied in the articles included in this thesis. In the first problem the goal is to determine distances from points, called study points, to shorelines in predefined directions. Together with other in-formation, mainly related to wind, these distances can be used to estimate wave exposure at different areas. In the second problem the input consists of a set of sites where water quality observations have been made and of the results of the measurements at the different sites. The goal is to select a subset of the observational sites in such a manner that water quality is still measured in a sufficient accuracy when monitoring at the other sites is stopped to reduce economic cost. Most of the thesis concentrates on the first problem, known as the fetch length problem. The main challenge is that the two-dimensional map is represented as a set of polygons with millions of vertices in total and the distances may also be computed for millions of study points in several directions. Efficient algorithms are developed for the problem, one of them approximate and the others exact except for rounding errors. The solutions also differ in that three of them are targeted for serial operation or for a small number of CPU cores whereas one, together with its further developments, is suitable also for parallel machines such as GPUs.

Von Neumann-Morgenstern Stable Sets in Matching Problems

The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable sets in one-to-one matching problem only if it is a maximal set satisfying the following properties : (a) the core is a subset of the set; (b) the set is a lattice; (c) the set of unmatched agents is identical for any two matchings belonging to the set. Furthermore, a set is a stable set if it is the unique maximal set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.

A Study Of Frames In The Fuzzy And Intuitionist Fuzzy Contexts

The fuzzy set theory has a wider scope of applicability than classical set theory in solving various problems. Fuzzy set theory in the last three decades as a formal theory which got formalized by generalizing the original ideas and concepts in classical mathematical areas and as a very powerful modeling language, that can cope with a large fraction of uncertainties of real life situations. In Intuitionistic Fuzzy sets a new component degree of non membership in addition to the degree of membership in the case of fuzzy sets with the requirement that their sum be less than or equal to one. The main objective of this thesis is to study frames in Fuzzy and Intuitionistic Fuzzy contexts. The thesis proved some results such as ifµ is a fuzzy subset of a frame F, then µ is a fuzzy frame of F iff each non-empty level subset µt of µ is a subframe of F, the category Fuzzfrm of fuzzy frames has products and the category Fuzzfrm of fuzzy frames is complete. It define a fuzzy-quotient frame of F to be a fuzzy partition of F, that is, a subset of IF and having a frame structure with respect to new operations and study the notion of intuitionistic fuzzy frames and obtain some results and introduce the concept of Intuitionistic fuzzy Quotient frames. Finally it establish the categorical link between frames and intuitionistic fuzzy topologies.

Two-point boundary value problems for linear evolution equations

We study boundary value problems for a linear evolution equation with spatial derivatives of arbitrary order, on the domain 0 < x < L, 0 < t < T, with L and T positive nite constants. We present a general method for identifying well-posed problems, as well as for constructing an explicit representation of the solution of such problems. This representation has explicit x and t dependence, and it consists of an integral in the k-complex plane and of a discrete sum. As illustrative examples we solve some two-point boundary value problems for the equations iqt + qxx = 0 and qt + qxxx = 0.

On the spectra of certain integro-differential-delay problems with applications in neurodynamics

We investigate the spectrum of certain integro-differential-delay equations (IDDEs) which arise naturally within spatially distributed, nonlocal, pattern formation problems. Our approach is based on the reformulation of the relevant dispersion relations with the use of the Lambert function. As a particular application of this approach, we consider the case of the Amari delay neural field equation which describes the local activity of a population of neurons taking into consideration the finite propagation speed of the electric signal. We show that if the kernel appearing in this equation is symmetric around some point a= 0 or consists of a sum of such terms, then the relevant dispersion relation yields spectra with an infinite number of branches, as opposed to finite sets of eigenvalues considered in previous works. Also, in earlier works the focus has been on the most rightward part of the spectrum and the possibility of an instability driven pattern formation. Here, we numerically survey the structure of the entire spectra and argue that a detailed knowledge of this structure is important within neurodynamical applications. Indeed, the Amari IDDE acts as a filter with the ability to recognise and respond whenever it is excited in such a way so as to resonate with one of its rightward modes, thereby amplifying such inputs and dampening others. Finally, we discuss how these results can be generalised to the case of systems of IDDEs.

Symmetric Push-Sum Protocol for decentralised aggregation

Gossip (or Epidemic) protocols have emerged as a communication and computation paradigm for large-scale networked systems. These protocols are based on randomised communication, which provides probabilistic guarantees on convergence speed and accuracy. They also provide robustness, scalability, computational and communication efficiency and high stability under disruption. This work presents a novel Gossip protocol named Symmetric Push-Sum Protocol for the computation of global aggregates (e.g., average) in decentralised and asynchronous systems. The proposed approach combines the simplicity of the push-based approach and the efficiency of the push-pull schemes. The push-pull schemes cannot be directly employed in asynchronous systems as they require synchronous paired communication operations to guarantee their accuracy. Although push schemes guarantee accuracy even with asynchronous communication, they suffer from a slower and unstable convergence. Symmetric Push- Sum Protocol does not require synchronous communication and achieves a convergence speed similar to the push-pull schemes, while keeping the accuracy stability of the push scheme. In the experimental analysis, we focus on computing the global average as an important class of node aggregation problems. The results have confirmed that the proposed method inherits the advantages of both other schemes and outperforms well-known state of the art protocols for decentralized Gossip-based aggregation.