Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTime-free solution to independent set problem using P systems with active membranes
66
0
0.0
(
0
)
Added by
Bosheng Song
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Membrane computing is a branch of natural computingwhich abstracts fromthe structure and the functioning of living cells. The computation models obtained in the field of membrane computing are usually called P systems. P systems have been used to solve computationally hard problems efficiently on the assumption that the execution of each rule is completed in exactly one time-unit (a global clock is assumed for timing and synchronizing the execution of rules). However, in biological reality, different biological processes take different times to be completed, which can also be influenced by many environmental factors. In this work, with this biological reality, we give a time-free solution to independent set problemusing P systems with active membranes, which solve the problem independent of the execution time of the involved rules.
rate research
Read More
Goods formula and Fishers method are frequently used for combining independent P-values. Interestingly, the equivalent of Goods formula already emerged in 1910 and mathematical expressions relevant to even more general situations have been repeatedly derived, albeit in different context. We provide here a novel derivation and show how the analytic formula obtained reduces to the two aforementioned ones as special cases. The main novelty of this paper, however, is the explicit treatment of nearly degenerate weights, which are known to cause numerical instabilities. We derive a controlled expansion, in powers of differences in inverse weights, that provides both accurate statistics and stable numerics.
The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theorem. However, the complexity of computing a maximum independent set (MIS) is a long-standing open question in even-hole-free graphs. From the hardness point of view, MIS is W[1]-hard in the class of graphs without induced 4-cycle (when parameterized by the solution size). Halfway of these, we show in this paper that MIS is FPT when parameterized by the solution size in the class of even-hole-free graphs. The main idea is to apply twice the well-known technique of augmenting graphs to extend some initial independent set.
Despite the ultraviolet problems with canonical quantum gravity, as an effective field theory its infrared phenomena should enjoy fully quantum mechanical unitary time evolution. Currently this is not possible, the impediment being what is known as the problem of time. Here, we provide a solution by promoting the cosmological constant $Lambda$ to a Lagrange multiplier constraining the metric volume element to be manifestly a total derivative. Because $Lambda$ appears linearly in the Hamiltonian constraint, it unitarily generates time evolution, yielding a functional Schroedinger equation for gravity. Two pleasant side effects of this construction are that vacuum energy is dissociated from the cosmological constant problem, much like in unimodular gravity, and the natural foliation provided by the time variable defines a sensible solution to the measure problem of eternal inflation.
Let $G$ be a graph on $n$ vertices and $mathrm{STAB}_k(G)$ be the convex hull of characteristic vectors of its independent sets of size at most $k$. We study extension complexity of $mathrm{STAB}_k(G)$ with respect to a fixed parameter $k$ (analogously to, e.g., parameterized computational complexity of problems). We show that for graphs $G$ from a class of bounded expansion it holds that $mathrm{xc}(mathrm{STAB}_k(G))leqslant mathcal{O}(f(k)cdot n)$ where the function $f$ depends only on the class. This result can be extended in a simple way to a wide range of similarly defined graph polytopes. In case of general graphs we show that there is {em no function $f$} such that, for all values of the parameter $k$ and for all graphs on $n$ vertices, the extension complexity of $mathrm{STAB}_k(G)$ is at most $f(k)cdot n^{mathcal{O}(1)}.$ While such results are not surprising since it is known that optimizing over $mathrm{STAB}_k(G)$ is $FPT$ for graphs of bounded expansion and $W[1]$-hard in general, they are also not trivial and in both cases stronger than the corresponding computational complexity results.
We are given a set $A$ of buyers, a set $B$ of houses, and for each buyer a preference list, i.e., an ordering of the houses. A house allocation is an injective mapping $tau$ from $A$ to $B$, and $tau$ is strictly better than another house allocation $tau eq tau$ if for every buyer $i$, $tau(i)$ does not come before $tau(i)$ in the preference list of $i$. A house allocation is Pareto optimal if there is no strictly better house allocation. Let $s(tau)$ be the image of $tau$ (i.e., the set of houses sold in the house allocation $tau$). We are interested in the largest possible cardinality $f(m)$ of the family of sets $s(tau)$ for Pareto optimal mappings $tau$ taken over all sets of preference lists of $m$ buyers. We improve the earlier upper bound on $f(m)$ given by Asinowski, Keszegh and Miltzow by making a connection between this problem and some problems in extremal set theory.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
