1.0957-Approximation Algorithm for Random MAX-3SAT
We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.
A broadcasting algorithm with time and message optimum on arrangement graphs.
A. C. Clarke's Space Odyssey and Newton's law of gravity
In his famous tetralogy, Space Odyssey, A. C. Clarke called the calculation of a motion of a mass point in the gravitational field of the massive cuboid a classical problem of gravitational mechanics. This article presents a proposal for a solution to this problem in terms of Newton's theory of gravity. First we discuss and generalize Newton's law of gravitation. We then compare the gravitational field created by the cuboid -- monolith, with the gravitational field of the homogeneous sphere. This...
A characterization of the set of fixed points of the quicksort transformation.
A combinatorial ranking problem.
A combinatorial ranking problem. (Short Communication).
A comparison of multiobjective evolutionary algorithms.
A complete characterization of primitive recursive intensional behaviours
We give a complete characterization of the class of functions that are the intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic case of recursion. This result is obtained using the property of ultimate unarity and a geometrical approach of sequential functions on N the set of positive integers.
A Complexity Calculus for Recursive Tree Algorithms
A computation of positive one-peak posets that are Tits-sincere
A complete list of positive Tits-sincere one-peak posets is provided by applying combinatorial algorithms and computer calculations using Maple and Python. The problem whether any square integer matrix is ℤ-congruent to its transpose is also discussed. An affirmative answer is given for the incidence matrices and the Tits matrices of positive one-peak posets I.
A Computer Algebra Application to Determination of Lie Symmetries of Partial Differential Equations
The paper has been presented at the 12th International Conference on Applications of Computer Algebra, Varna, Bulgaria, June, 2006A MATHEMATICA package for finding Lie symmetries of partial differential equations is presented. The package is designed to create and solve the associated determining system of equations, the full set of solutions of which generates the widest permissible local Lie group of point symmetry transformations. Examples illustrating the functionality of the package's tools...
A conception of optimality for algorithms and its application to the optimal search for a minimum
A defuzzification based new algorithm for the design of Mamdani-type fuzzy controllers
This paper presents a new learning algorithm for the design of Mamdani- type or fully-linguistic fuzzy controllers based on available input-output data. It relies on the use of a previously introduced parametrized defuzzification strategy. The learning scheme is supported by an investigated property of the defuzzification method. In addition, the algorithm is tested by considering a typical non-linear function that has been adopted in a number of published research articles. The test stresses on...
A distributed transportation simplex applied to a Content Distribution Network problem
A Content Distribution Network (CDN) can be defined as an overlay system that replicates copies of contents at multiple points of a network, close to the final users, with the objective of improving data access. CDN technology is widely used for the distribution of large-sized contents, like in video streaming. In this paper we address the problem of finding the best server for each customer request in CDNs, in order to minimize the overall cost. We consider the problem as a transportation problem...
A distributed voting scheme to maximize preferences
We study the problem of designing a distributed voting scheme for electing a candidate that maximizes the preferences of a set of agents. We assume the preference of agent i for candidate j is a real number xi,j, and we do not make any assumptions on the mechanism generating these preferences. We show simple randomized voting schemes guaranteeing the election of a candidate whose expected total preference is nearly the highest among all candidates. The algorithms we consider are designed so that...
A factor-two approximation algorithm for two-dimensional phase unwrapping.
A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures
In this paper, we demonstrate the computational consequences of making a simple assumption on production cost structures in capacitated lot-size problems. Our results indicate that our cost assumption of increased productivity over time has dramatic effects on the problem sizes which are solvable. Our experiments indicate that problems with more than 1000 products in more than 1000 time periods may be solved within reasonable time. The Lagrangian decomposition algorithm we use does of course not...
A formal analysis of the computational dynamics in GIGANTEC.
An evolutionary algorithm formalism has been forwarded in a previous research, and implemented in the system GIGANTEC: Genetic Induction for General Analytical Non-numeric Task Evolution Compiler [Bad98][Bad99]. A dynamical model is developed to analyze the behaviour of the algorithm. The model is dependent in its analysis on classical Compilers Theory, Game Theory and Markov Chains and its convergence characteristics. The results conclude that a limiting state is reached, which is independent of...
A generalization of Gosper's algorithm to bibasic hypergeometric summation.
A heuristical algorithm for simple exponential analysis