23,183 research outputs found
Low-rank matrix approximation with weights or missing data is NP-hard
No full textWeighted low-rank approximation (WLRA), a dimensionality reduction technique for data analysis, has been successfully used in several applications, such as in collaborative filtering to design recommender systems or in computer vision to recover structure from motion. In this paper, we study the computational complexity of WLRA and prove that it is NP-hard to find an approximate solution, even when a rank-one approximation is sought. Our proofs are based on a reduction from the maximum-edge biclique problem, and apply to strictly positive weights as well as binary weights (the latter corresponding to low-rank matrix approximation with missing data).low-rank matrix approximation, weighted low-rank approximation, missing data, matrix completion with noise, PCA with missing data, computational complexity, maximum-edge biclique problem
Numerical evidence for phase transitions of NP-complete problems for instances drawn from Lévy-stable distributions
No full textRandom NP-Complete problems have come under study as an important tool used in the analysis
of optimization algorithms and help in our understanding of how to properly address issues of
computational intractability.
In this thesis, the Number Partition Problem and the Hamiltonian Cycle Problem are taken as
representative NP-Complete classes. Numerical evidence is presented for a phase transition in the
probability of solution when a modified Lévy-Stable distribution is used in instance creation for each.
Numerical evidence is presented that show hard random instances exist near the critical threshold
for the Hamiltonian Cycle problem. A choice of order parameter for the Number Partition Problem’s
phase transition is also given.
Finding Hamiltonian Cycles in Erdös-Rényi random graphs is well known to have almost sure polynomial time algorithms, even near the critical threshold. To the author’s knowledge, the graph
ensemble presented is the first candidate, without specific graph structure built in, to generate
graphs whose Hamiltonicity is intrinsically hard to determine. Random graphs are chosen via their
degree sequence generated from a discretized form of Lévy-Stable distributions. Graphs chosen from
this distribution still show a phase transition and appear to have a pickup in search cost for the
algorithms considered. Search cost is highly dependent on the particular algorithm used and the
graph ensemble is presented only as a potential graph ensemble to generate intrinsically hard graphs
that are difficult to test for Hamiltonicity.
Number Partition Problem instances are created by choosing each element in the list from a modified
Lévy-Stable distribution. The Number Partition Problem has no known good approximation algorithms and so only numerical evidence to show the phase transition is provided without considerable
focus on pickup in search cost for the solvers used. The failure of current approximation algorithms
and potential candidate approximation algorithms are discussed
np-CECADA: Enhancing Ubiquitous Connectivity of LoRa Networks
No full textLong Range Wide Area Networks (LoRaWAN) offer ubiquitous communications for The Internet of Things (IoT). However, there are many challenges in rolling out LoRaWAN - mainly scalability, energy efficiency, Packet Reception Ratio (PRR), and keeping the channel access as simple as unslotted ALOHA. To this end, we design non-persistent Capture Effect Channel Activity Detection Algorithm (np-CECADA), which is a novel, distributed protocol for the MAC layer of LoRaWAN. It utilizes Channel Activity Detection (CAD), which is a built-in imperfect mechanism for channel sensing and minimal feedback from the gateways. In np-CECADA each device independently adapts backoff times based on the traffic in its vicinity and the transmission power based on the heuristically inferred probability of capturing the channel. To achieve this, first, we carried out an extensive on-field evaluation to measure the effectiveness of CAD and capture effect in LoRa. Using them we designed np CECADA and developed ns-3 modules. Packet Reception Ratio of np-CECADA is 15.74× and 5.13× higher than vanilla LoRaWAN and p-CARMA, respectively. Channel utilization is 11.24× higher compared to LMAC. Further, on a testbed of 30 LoRa devices np-CECADA outperforms LoRaWAN up to 5 times.Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Embedded System
Summary statistics of <i>Nannochloropsis</i> growth in low-NP and high-NP medium.
No full textSummary statistics of Nannochloropsis growth in low-NP and high-NP medium.</p
Improved adjuvanting of seasonal influenza vaccines: Pre-clinical studies of MVA-NP+M1 co-administration with inactivated influenza vaccine.
No full textLicensed seasonal influenza vaccines induce antibody responses against influenza hemagglutinin that are limited in their ability to protect against different strains of influenza. Cytotoxic T lymphocytes (CTLs) recognizing the conserved internal nucleoprotein (NP) and matrix protein (M1) are capable of mediating a cross-subtype immune response against influenza. Modified vaccinia virus Ankara encoding NP and M1 (MVA-NP+M1) is designed to boost pre-existing T-cell responses in adults in order to elicit a cross-protective immune response. We examined the co-administration of hemagglutinin (HA) protein formulations and candidate MVA-NP+M1 influenza vaccines in murine, avian, and swine models. Antibody responses post-immunization were measured by ELISA and pseudotype neutralization assays. Here we demonstrate that MVA-NP+M1 can act as an adjuvant enhancing antibody (Ab) responses to HA while simultaneously inducing potent T-cell responses to conserved internal antigens. We show that this regimen leads to the induction of cytophilic Ab isotypes that are capable of inhibiting hemagglutination and in the context of H5 exhibit cross-clade neutralization. The simultaneous induction of T cells and antibody responses has the potential to improve seasonal vaccine performance and could be employed in pandemic situations
PCET-driven Reactivity of Neptunyl(VI) Yields Oxo-bridged Np(V) and Np(IV) Species
No full textA reaction sequence based upon the principles of proton-coupled electron transfer (PCET) has been used to access two unconventional oxo-deficient polynuclear complexes of neptunium (Np). The complexes featuring mono-μ2-oxo motifs assemble under ambient atmosphere upon dissolution of neptunyl(VI) diacetate dihydrate (NpO2(OAc)2(H2O)2·HOAc) in methanol followed by addition of a supporting pentadentate ligand (LNM); one complex is a mixed-valent [NpV,NpIV,NpV ] trimer with two bridging μ2-oxos and the other is a [NpV,NpV ] dimer featuring a single μ2-oxo. The outer Np centers are also capped with terminal oxo ligands. Spectroscopic and spectrokinetic findings show that intermediate [NpV O2(OAc)]n species form prior to metal chelation by LNM; electrolysis experiments demonstrate that production of Np(V) gives rise to asynchronous proton transfer that does not occur otherwise (in the Np(VI) state) as well as condensation (loss of H2O) and formation of the polynuclear complexes. The oxo-deficient nature of these products is attributable to the reduction/condensation reaction sequence of PCET. Consequently, PCET reactivity appears poised to complement more established techniques for interconverting actinide oxidation states, a prospect with considerable applications in fuel recycling for low-carbon nuclear energy
Complexity of approximating bounded variants of optimization problems
No full textAbstractWe study low degree graph problems such as Maximum Independent Set and Minimum Vertex Cover. The goal is to improve approximation lower bounds for them and for a number of related problems like Max-B-Set Packing, Min-B-Set Cover, and Max-B-Dimensional Matching, B⩾3. We prove, for example, that it is NP-hard to achieve an approximation factor of 9594 for Max-3-DM, and a factor of 4847 for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element
NP-led obesity clinics: a NP guided primary care approach for managing obesity in low income preschool-age children in Canada
No full textChildhood obesity continues to increase at alarming rates despite health prevention efforts to date. New innovative approaches are needed to help address this public health concern. Moreover, current literature confirms that early childhood is a fundamental time for establishing life behaviors that will follow into adulthood thus, the early years are considered to be an essential stage for developing both an unhealthy weight and its precursor behaviors. Social circumstances including socioeconomic status greatly impact health and are notable risk factors for the development of obesity. Acknowledging sociological influences and working within these constructs helps to create programs and care plans that are contextual. The purpose of this paper is to explore the role of nurse practitioners when working with low income families to address childhood obesity in the preschool-aged population in Canada, specifically within the setting of a NP-led obesity clinic. Literature to date does not exist for NP-led obesity clinics as this is a proposed approach to helping combat pediatric obesity. Existing literature regarding nurse-managed health centers and pediatric weight management programs were utilized to support the creation of a NP-led obesity clinic. Nurse-managed health centers have established that NPs are capable of providing appropriate medical treatment with positive health outcomes. Further, level of patient satisfaction and quality of care provided at nurse-managed health centers either met or exceeded national benchmarks for care. Pediatric weight management programs are in the infancy phase in Canada but have demonstrated positive weight management outcomes. Existing Canadian programs are informally evaluated to provide further support for the use of NP-led obesity clinics within the current Canadian health care system. This paper proposes that NP-led obesity clinics are a novel approach to help address childhood obesity within the primary care environment. --Leaf 2.The original print copy of this thesis may be available here: http://wizard.unbc.ca/record=b183577
A low and a high hierarchy within NP
No full textAbstractA low and a high hierarchy within NP are defined. The definition is similar to the jump hierarchies below the degree of the halting problem. For this purpose a complexity theoretic counterpart of the jump operator in recursion theory is defined. Some elementary properties of these hierarchies are investigated. The high hierarchy is, in some sense, a hierarchy of generalized NP-completeness notions
- …
