Resolution-based lower bounds in MaxSAT

The lower bound (LB) implemented in branch and bound MaxSAT solvers is decisive for obtaining a competitive solver. In modern solvers like MaxSatz and MiniMaxSat, the LB relies on the cooperation of the underestimation and inference components. Actually, the underestimation component of some solvers guides the application of the inference component when a conflict is reached and certain structures are found. In this paper we analyze algorithmic and logical aspects of the underestimation components that have been implemented in MaxSatz during its evolution. From an algorithmic point of view, we define novel strategies for selecting unit clauses in UP (the underestimation of LB in UP is the number of independent inconsistent subformulas detected using unit propagation), the extension of UP with failed literal detection, and a clever heuristic for guiding the application of MaxSAT resolution when UP augmented with failed literal detection is applied in the presence of cycles structures. From a logical point of view, we prove that the inconsistent subformulas detected by UP are minimally unsatisfiable, but this property does not hold if failed literal detection is added. In the presence of cycle structures in conflicts detected by UP augmented with failed literal detection, we prove that the application of MaxSAT resolution produces smaller inconsistent subformulas and, besides, generates additional clauses that may be used to improve the LB. The conducted empirical investigation indicates that the LB techniques described in this paper lead to better quality LBs.     

Spontaneous Outcropping of Self‐Assembled Insulating Nanodots in Solution‐Derived Metallic Ferromagnetic La0.7Sr0.3MnO3 Films

A new mechanism is proposed for the generation of self‐assembled nanodots at the surface of a film based on spontaneous outcropping of the secondary phase of a nanocomposite epitaxial film. Epitaxial self‐assembled Sr–La oxide insulating nanodots are formed through this mechanism at the surface of an epitaxial metallic ferromagnetic La_0.7Sr_0.3MnO₃ (LSMO) film grown on SrTiO₃ from chemical solutions. TEM analysis reveals that, underneath the La–Sr oxide (LSO) nanodots, the film switches from the compressive out‐of‐plane stress component to a tensile one. It is shown that the size and concentration of the nanodots can be tuned by means of growth kinetics and through modification of the La excess in the precursor chemical solution. The driving force for the nanodot formation can be attributed to a cooperative effect involving the minimization of the elastic strain energy and a thermodynamic instability of the LSMO phase against the formation of a Ruddelsden–Popper phase Sr₃Mn₄O₇ embedded in the film, and LSO surface nanodots. The mechanism can be described as a generalization of the classical Stranski–Krastanov growth mode involving phase separation. LSO islands induce an isotropic strain to the LSMO film underneath the island which decreases the magnetoelastic contribution to the magnetic anisotropy.     

Cross-Layer Fast Link Adaptation for MIMO-OFDM Based WLANs

This paper considers the use of cross-layer fast link adaptation (FLA) for WLANs employing a MIMO-OFDM physical layer. A packet error rate (PER)-based FLA technique that, without loss of generality, makes use of the exponential effective SNR mapping (EESM) is proposed. Additionally, an FLA scheme relying on bit error rate (BER) metrics is introduced that simplifies the link adaptation procedure without any significant performance degradation. Results show that both PER- and BER-based FLA techniques optimize the data throughput while satisfying prescribed quality of service constraints. Channel estimation errors have also been considered, revealing the importance of good channel estimators in order for FLA strategies to work satisfactorily.     

Exact Algorithms for MAX-SAT

The maximum satisfiability problem (MAX-SAT) is stated as follows: Given a boolean formula in CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-SAT is MAX-SNP-complete and received much attention recently. One of the challenges posed by Alber, Gramm and Niedermeier in a recent survey paper asks: Can MAX-SAT be solved in less than 2ⁿ “steps”? Here, n is the number of distinct variables in the formula and a step may take polynomial time of the input. We answered this challenge positively by showing that a popular algorithm based on branch-and-bound is bounded by O(2ⁿ) in time, where n is the maximum number of occurrences of any variable in the input.When the input formula is in 2-CNF, that is, each clause has at most two literals, MAX-SAT becomes MAX-2-SAT and the decision version of MAX-2-SAT is still NP-complete. The best bound of the known algorithms for MAX-2-SAT is O(m2^m/5), where m is the number of clauses. We propose an efficient decision algorithm for MAX-2-SAT whose time complexity is bound by O(n2ⁿ). This result is substantially better than the previously known results. Experimental results also show that our algorithm outperforms any algorithm we know on MAX-2-SAT.