### 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.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.

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...

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 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 $A\in \u2099\left(\mathbb{Z}\right)$ is ℤ-congruent to its transpose ${A}^{tr}$ is also discussed. An affirmative answer is given for the incidence matrices ${C}_{I}$ and the Tits matrices $C{\u0302}_{I}$ of positive one-peak posets I.

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...

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 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...

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...

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...

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...