Approximation algorithms for DNF under distributions with limited independence

In this paper we investigate the problem of approximating the fraction of truth assignments that satisfy a Boolean formula with some restricted form of DNF under distributions with limited independence between random variables. LetF be a DNF formula onn variables withm clauses in which each literal appears at most once. We prove that ifD is [k logm]-wise independent, then |Pr _D [F]-Pr _U [F]| ≤ , whereU denotes the uniform distribution and Pr _D [F] denotes the probability thatF is satisfied by a truth assignment chosen according to distributionD (similarly for Pr _U [F]). Using the result, we also derive the following: For formulas satisfying the restriction described above and for any constantc, there exists a probability distributionD, with size polynomial in logn andm, such that |Pr _D [F] - Pr _U [F]| ≤c holds.     

Three-machine flowshop with two operations per job to minimize makespan

This work studies three variants of a three-machine flowshop problem with two operations per job to minimize makespan (F3/o = 2/C_max). A set of n jobs are classified into three mutually exclusive families A, B and C. The families A, B and C are defined as the set of jobs that is scheduled in machine sequence (M₁, M₂), (M₁, M₃) and (M₁, M₃), respectively, where (M_x, M_y) specifies the machine sequence for the job that is processed first on M_x, and then on M_y. Specifically, jobs with the same route (machine sequence) are classified into the same family. Three variants of F3/o = 2/C_max are studied. First, F3/GT, no-idle, o = 2/C_max, in which both machine no-idle and GT restrictions are considered. The GT assumption requires that all jobs in the same family are processed contiguously on the machine and the machine no-idle assumption requires that all machines work continuously without idle time. Second, the problem F3/GT, o = 2/C_max, in which the machine no-idle restriction in the first variant is relaxed, is considered. Third, the problem F3/no-idle, o = 2/C_max with the GT assumption in the first variant relaxed is considered. Based on the dominance conditions developed, the optimal solution is polynomially derived for each variant. These results may narrow down the gap between easy and hard cases of the general problem.     

A characterization of residual implications derived from left-continuous uninorms

In this paper, a set of axioms is given that characterizes those functions I:[0, 1]² → [0, 1] for which a left-continuous uninorm U exists in such a way that I is the residual implication derived from U. A characterization for the particular cases when U is representable, when U is continuous in ]0,1[² and when U is idempotent are also given.     

On mimicking networks representing minimum terminal cuts

Given a capacitated undirected graph G=(V,E)$G=(V,E)$ with a set of terminals K⊂V$K\subset V$, a mimicking network   is a smaller graph H=(_VH,_EH)$H=(V_H,E_H)$ which contains the set of terminals K   and for every bipartition [U,K−U]$[U,K-U]$ of the terminals, the cost of the minimum cut separating U   from K−U$K-U$ in G is exactly equal to the cost of the minimum cut separating U   from K−U$K-U$ in H.     

Hamiltonian laceability of bubble-sort graphs with edge faults

It is known that the n-dimensional bubble-sort graph B_n is bipartite, (n − 1)-regular, and has n! vertices. We first show that, for any vertex v, B_n − v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of B_n. We next show that B_n − F has a hamiltonian path between any two vertices of different partite sets if ∣F∣ is at most n − 3. Then we also prove that B_n − F has a path of length n! − 2 between any pair of vertices in the same partite set.     

Parameterizing cut sets in a graph by the number of their components

For a connected graph G=(V,E), a subset U⊆V is a disconnected cut if U disconnects G and the subgraph G[U] induced by U is disconnected as well. A cut U is a k-cut if G[U] contains exactly k(≥1) components. More specifically, a k-cut U is a (k,?)-cut if V?U induces a subgraph with exactly ?(≥2) components. The Disconnected Cut problem is to test whether a graph has a disconnected cut and is known to be NP-complete. The problems k-Cut and (k,?)-Cut are to test whether a graph has a k-cut or (k,?)-cut, respectively. By pinpointing a close relationship to graph contractibility problems we show that (k,?)-Cut is in P for k=1 and any fixed constant ?≥2, while it is NP-complete for any fixed pair k,?≥2. We then prove that k-Cut is in P for k=1 and NP-complete for any fixed k≥2. On the other hand, for every fixed integer g≥0, we present an FPT algorithm that solves (k,?)-Cut on graphs of Euler genus at most g when parameterized by k+?. By modifying this algorithm we can also show that k-Cut is in FPT for this graph class when parameterized by k. Finally, we show that Disconnected Cut is solvable in polynomial time for minor-closed classes of graphs excluding some apex graph.     

Cyclic codes over R = Fp + uFp +?+ uFp with length pn

In this paper, all cyclic codes with length p^sn, (n prime to p) over the ring R = F_p + uF_p +?+ u^k−1F_p are classified. It is first proved that Tor_j(C) is an ideal of , so that the structure of ideals over extension ring S_u^k(m,ω)=GR(u^k,m)[ω]/〈ω^ps-1〉 is determined. Then, an isomorphism between R[X]/〈X^N − 1〉 and a direct sum ⊕_h∈IS_u^k(m_h,ω) can be obtained using discrete Fourier transform. The generator polynomial representation of the corresponding ideals over F_p + uF_p +?+ u^k−1F_p is calculated via the inverse isomorphism. Moreover, torsion codes, MS polynomial and inversion formula are described.     

Computer-assisted existence proofs for two-point boundary value problems

For (scalar) nonlinear two-point boundary value problems of the form?U ^{″+F(x, U, U′)} =0, B ₀ [U]=B ₁ [U]=0, with Sturm-Liouville or periodic boundary operatorsB ₀ andB ₁, we present a method for proving the existence of a solution within a “close”C ₁-neighborhood of an approximate solution.     

The panpositionable panconnectedness of augmented cubes

A graph G is panconnected if, for any two distinct vertices x and y of G, it contains an [x, y]-path of length l for each integer l satisfying d_G(x, y) ? l ? ∣V(G)∣ − 1, where d_G(x, y) denotes the distance between vertices x and y in G, and V(G) denotes the vertex set of G. For insight into the concept of panconnectedness, we propose a more refined property, namely panpositionable panconnectedness. Let x, y, and z be any three distinct vertices in a graph G. Then G is said to be panpositionably panconnected if for any d_G(x, z) ? l₁ ? ∣V(G)∣ − d_G(y, z) − 1, it contains a path P such that x is the beginning vertex of P, z is the (l₁ + 1)th vertex of P, and y is the (l₁ + l₂ + 1)th vertex of P for any integer l₂ satisfying d_G(y, z) ? l₂ ? ∣V(G)∣ − l₁ − 1. The augmented cube, proposed by Choudum and Sunitha [6] to be an enhancement of the n-cube Q_n, not only retains some attractive characteristics of Q_n but also possesses many distinguishing properties of which Q_n lacks. In this paper, we investigate the panpositionable panconnectedness with respect to the class of augmented cubes. As a consequence, many topological properties related to cycle and path embedding in augmented cubes, such as pancyclicity, panconnectedness, and panpositionable Hamiltonicity, can be drawn from our results.     

Edge-pancyclicity and path-embeddability of bijective connection graphs

An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2ⁿ nodes and n2ⁿ⁻¹ edges. The n-dimensional hypercube, crossed cube, Möbius cube, etc. are some examples of the n-dimensional BC graphs. In this paper, we propose a general method to study the edge-pancyclicity and path-embeddability of the BC graphs. First, we prove that a path of length l with dist(X_n, x, y) + 2 ? l ? 2ⁿ − 1 can be embedded between x and y with dilation 1 in X_n for x, y ∈ V(X_n) with x ≠ y in X_n, where X_n (n ? 4) is a n-dimensional BC graph satisfying the three specific conditions and V(X_n) is the node set of X_n. Furthermore, by this result, we can claim that X_n is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also other BC graphs except crossed cubes and Möbius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Möbius cubes.     

High performance polymer actuator based on carbon nanotube-ionic liquid gel: Effect of ionic liquid

In this study, we investigated a dependence of anionic species of ionic liquids (ILs) (IL: perfluoroalkyltrifluoroborate anions ([C_nF_2n+1BF₃]⁻ (n = 0, 1, 2) and bis(perfluoroalkylsulfonyl)imide anions ([(C_mF_2m+1SO₂)(C_nF_2n+1SO₂)N]⁻ (m, n = 0, 1, 2)) on electrochemical and electromechanical properties. 1-Ethyl-3-methylimidazolium (EMI⁺) was selected as a cation for ILs. 1-Ethyl-3-methylimidazolium trifluoromethyltrifluoroborate (EMI[CF₃BF₃]), 1-ethyl-3-methylimidazolium pentafluoroethyltrifluoroborate (EMI[CF₃CF₂BF₃]), 1-ethyl-3-methylimidazolium fluorosulfonyl(trifluoromethylsulfonyl)imide (EMI[FTA]) and 1-ethyl-3-methylimidazolium pentafluoroethylsulfonyl(trifluoromethylsulfonyl)imide (EMI[C₁C₂]) were synthesized according to the literatures. The generated strains of the bucky-gel electrodes of the actuators containing EMI[CF₃BF₃] (in the high frequency range: 10-0.5 Hz) and EMI[CF₃CF₂BF₃] (in the high frequency range of 1-0.5 Hz) are larger than that containing EMI[BF₄] (that is to say the quick response). For low frequencies (0.1-0.005 Hz), the generated strain containing EMI[CF₃CF₂BF₃] was larger than those containing other ILs (EMI[C_nF_2n+1BF₃] (n = 0, 1) and EMI[(C_mF_2m+1SO₂)(C_nF_2n+1SO₂)N] (m, n = 0, 1, 2)). The Young's modulus of actuators containing EMI[CF₃BF₃] and EMI[CF₃CF₂BF₃] were 145 and 110 MPa, respectively. The melting points of EMI[CF₃BF₃] and EMI[CF₃CF₂BF₃] are lower than that of EMI[BF₄].Therefore, trifluoromethyltrifluoroborate ([CF₃BF₃]⁻) and pentafluoroethyltrifluoroborate ([CF₃CF₂BF₃]⁻) anions performed much better as the actuator using the polymer-supported bucky-gel electrode containing the IL. These results are considered to be the actuator enough to apply actual applications (e.g. tactile display).     

Development of a tundra-specific snow water equivalent retrieval algorithm for satellite passive microwave data

Airborne and satellite brightness temperature (T_B) measurements were combined with intensive field observations of sub-Arctic tundra snow cover to develop the framework for a new tundra-specific passive microwave snow water equivalent (SWE) retrieval algorithm. The dense snowpack and high sub-grid lake fraction across the tundra mean that conventional brightness temperature difference approaches (such as the commonly used 37 GHz-19 GHz) are not appropriate across the sub-Arctic. Airborne radiometer measurements (with footprint dimensions of approximately 70 × 120 m) acquired across sub-Arctic Canada during three field campaigns during the 2008 winter season were utilized to illustrate a slope reversal in the 37 GHz T_B versus SWE relationship. Scattering by the tundra snowpack drives a negative relationship until a threshold SWE value is reached near 130 mm at which point emission from the snowpack creates a positive but noisier relationship between 37 GHz T_B and SWE.The change from snowpack scattering to emission was also evident in the temporal evolution of 37 GHz T_B observed from satellite measurements. AMSR-E brightness temperatures (2002/03-2006/07) consistently exhibited decreases through the winter before reaching a minimum in February or March, followed by an increase for weeks or months before melt. The cumulative absolute change (Σ|Δ37V|) in vertically polarized 37 GHz T_B was computed at both monthly and pentad intervals from a January 1 start date and compared to ground measured SWE from intensive and regional snow survey campaigns, and climate station observations. A greater (lower) cumulative change in |Δ37V| was significantly related to greater (lower) ground measured SWE (r² = 0.77 with monthly averages; r² = 0.67 with pentad averages). Σ|Δ37V| was only weakly correlated with lake fraction: monthly r² values calculated for January through April 2003-2007 were largely less than 0.2. These results indicate that this is a computationally straightforward and viable algorithmic framework for producing tundra-specific SWE datasets from the complete satellite passive microwave record (1979 to present).     

On a new class of fuzzy implications: h-Implications and generalizations

A new class of fuzzy implications called the h-implications is introduced. They are implications generated from an additive generator of a representable uninorm in a similar way of Yager’s f- and g-implications which are generated from additive generators of continuous Archimedean t-norms and t-conorms. Basic properties of these implications are studied in detail. Modifications and generalizations of the initial definition are presented and their properties studied and compared between them. One of the modifications, called (h, e)-implications, is another example of a fuzzy implication satisfying the exchange principle but not the law of importation for any t-norm, in fact for any function F : [0, 1]² → [0, 1].     

A Landsat time series approach to characterize bark beetle and defoliator impacts on tree mortality and surface fuels in conifer forests

Insects are important forest disturbance agents, and mapping their effects on tree mortality and surface fuels represents a critical research challenge. Although various remote sensing approaches have been developed to monitor insect impacts, most studies have focused on single insect agents or single locations and have not related observed changes to ground-based measurements. This study presents a remote sensing framework to (1) characterize spectral trajectories associated with insect activity of varying duration and severity and (2) relate those trajectories to ground-based measurements of tree mortality and surface fuels in the Cascade Range, Oregon, USA. We leverage a Landsat time series change detection algorithm (LandTrendr), annual forest health aerial detection surveys (ADS), and field measurements to investigate two study landscapes broadly applicable to conifer forests and dominant insect agents of western North America. We distributed 38 plots across multiple forest types (ranging from mesic mixed-conifer to xeric lodgepole pine) and insect agents (defoliator [western spruce budworm] and bark beetle [mountain pine beetle]). Insect effects were evident in the Landsat time series as combinations of both short- and long-duration changes in the Normalized Burn Ratio spectral index. Western spruce budworm trajectories appeared to show a consistent temporal evolution of long-duration spectral decline (loss of vegetation) followed by recovery, whereas mountain pine beetle plots exhibited both short- and long-duration spectral declines and variable recovery rates. Although temporally variable, insect-affected stands generally conformed to four spectral trajectories: short-duration decline then recovery, short- then long-duration decline, long-duration decline, long-duration decline then recovery. When comparing remote sensing data with field measurements of insect impacts, we found that spectral changes were related to cover-based estimates (tree basal area mortality [R²_adj = 0.40, F_1,34 = 24.76, P < 0.0001] and down coarse woody detritus [R²_adj = 0.29, F_1,32 = 14.72, P = 0.0006]). In contrast, ADS changes were related to count-based estimates (e.g., ADS mortality from mountain pine beetle positively correlated with ground-based counts [R²_adj = 0.37, F_1,22 = 14.71, P = 0.0009]). Fine woody detritus and forest floor depth were not well correlated with Landsat- or aerial survey-based change metrics. By characterizing several distinct temporal manifestations of insect activity in conifer forests, this study demonstrates the utility of insect mapping methods that capture a wide range of spectral trajectories. This study also confirms the key role that satellite imagery can play in understanding the interactions among insects, fuels, and wildfire.     

Computing Modular Invariants of p-groups

Let V be a finite dimensional representation of a p -group, G, over a field,k , of characteristic p. We show that there exists a choice of basis and monomial order for which the ring of invariants, k [ V ]^G, has a finite SAGBI basis. We describe two algorithms for constructing a generating set for k [ V ] G. We use these methods to analyse k [2V₃ ]^U₃where U₃is the p -Sylow subgroup ofGL₃ (F_p) and 2 V₃is the sum of two copies of the canonical representation. We give a generating set for k [2 V₃]^U₃forp =  3 and prove that the invariants fail to be Cohen–Macaulay forp >  2. We also give a minimal generating set for k [mV₂ ]^Z / pwere V₂is the two-dimensional indecomposable representation of the cyclic group Z / p.     

Affine-evasive sets modulo a prime

In this work, we describe a simple and efficient construction of a large subset S   of _Fp${\mathbb{F}}_p$, where p   is a prime, such that the set A(S)$A(S)$ for any non-identity affine map A   over _Fp${\mathbb{F}}_p$ has small intersection with S.     

Embedding meshes into locally twisted cubes

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ_n(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in LTQ_n with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in LTQ_n with dilation 1 and expansion 2. (3) For any integer n ? 3, a 4  × (2ⁿ⁻² − 1) mesh can be embedded in LTQ_n with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes.     

Biased scan of plasma display panel for data voltage reduction

This paper proposes a method of reducing the data voltage V_d of plasma display panels (PDPs). The proposed biased-scan method uses two separate ground systems: one for the sustain pulse generator (FGND) and the other for the data address and control systems (CHGND). A dc voltage bias, which is applied between CHGND and FGND during the address period, reduces V_d while preventing the undesired glow discharge induced by a scan pulse only. CHGND is connected to FGND for the first sustain pulse of each subfield, which reduces the time lag of address discharge, but it is separated from FGND for the other sustain pulses to increase the margin of the sustain voltage. The proposed method was tested on a 15% Xe 50-in. Full HD (1920 × 1080) single-scan PDP which had a sustain discharge gap of 110 μm. V_d could be reduced by 20 V (30%), and the power consumption of the V_d voltage source decreased by ∼25 W (50%) from that of the conventional method.     

On embedding cycles into faulty twisted cubes

The twisted cube TQ_n is an alternative to the popular hypercube network. Recently, some interesting properties of TQ_n were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let f_e and f_v be the numbers of faulty edges and faulty vertices in TQ_n, respectively. We show that, with f_e + f_v ? n − 2, a faulty TQ_n still contains a cycle of length l for every 4 ? l ? ∣V(TQ_n)∣ − f_v and odd integer n ? 3.     

Evaluation of three methodologies to estimate the VO2max in people of different ages

Aging and gender are factors that affect the variation of physical work capacity. The present paper highlights the importance of the metabolism used by ergonomics to establish the appropriate limits of loads at work. This study compares the aerobic capacity of people from 20 to 71 years old split in 5 different groups. The laboratory experiment tested 33 volunteers (19 women and 14 men). A submaximal step test was used to measure the VO₂ using a portable breath by breath metabolic system and a telemetric heart rate monitor. Three methods to estimate the VO_2max were compared: 1) a direct measurement of VO₂, 2) estimation by heart rate, and 3) a step test method using predetermined charts. Significant difference was encountered among the estimation methods as well as among the age ranges (F_2,92 = 6.43, p < 0.05 y F_4,92 = 7.18, p < 0.05 respectively). The method of direct measurement and the method of predetermined charts were different for the estimation of the VO_2max with a confidence level of 95%. The method of predetermined charts is better adapted for males and people younger than 30 years. The estimation through non invasive heart rate apparatus was a good appraiser of the maximal oxygen consumption considering both genders and all the age groups.