Back to Table of contents

Primeur weekly 2013-03-18

Exascale supercomputing

OFC/NFOEC features new research in low-power supercomputing, long-distance 400G data transmission, and simplified multicore fiber nanufacturing ...

Big Bang meets Big Data: South Africa joins ASTRON and IBM to build the foundation for a new era of computing ...

The Cloud

VMware outlines corporate strategy, innovations across software-defined data centre, hybrid Cloud and end-user computing ...

New Open Data Center Alliance White Paper highlights adoption of ODCA Cloud usage models ...

IBM helps Black Point Arts provide faster IT services through City Cloud ...

Desktop Grids

SubSetSum@Home project trying to solve NP-complete problem, known as Subset Sum ...

EuroFlash

451 Research Report: Will Energy Prices Power U.S. Datacentre Growth at Europe's Expense and Short-Circuit Energy Efficiency? ...

ClusterVision completes Top500 class HPC cluster at the University of Paderborn ...

New mathematical techniques allow simulations off-shore wind farms ...

Researchers wanted for The Big Data Challenge ...

PRACE's Open R&D HPC access for industry awarded in a European e-Infrastructure FP7 Project Success Story Competition ...

First Europe-China HPC Conference "Partnership for supercomputing applications in science and industry" ...

PRACE Scientific Conference 2013 to be hosted at ISC'13 in Leipzig ...

PRACE Spring School 2013 to address New and Emerging Technologies - Programming for Accelerators ...

PRACE Summer School 2013 to highlight Frameworks for Scientific Computing on Supercomputers ...

N8 HPC showcased to boost collaboration with industry ...

European Commission selects HP to prpvide mission-critical servers ...

Oracle's "Big Data Readiness Report" for Europe, Middle East and Russia now available ...

USFlash

Fujitsu and NAOJ Begin Operation of Supercomputer for ALMA ...

iVEC@Curtin creates one-stop-shop for IT services ...

DataDirect Networks delivers faster performance than Flash storage, improving trading algorithm development and risk management for financial services companies ...

IBM taps next generation leaders to fuel Watson innovations; USC students aim high in first-ever West Coast Case Competition ...

Quantum computing moves forward ...

Turing Award to the Weizmann Institute's Shafi Goldwasser ...

IBM Software helps Illinois Department of Human Services manage Big Data and transform operations ...

SubSetSum@Home project trying to solve NP-complete problem, known as Subset Sum

12 Mar 2013 Grand Forks - SubsetSum@Home, based at the University of North Dakota Computer Science Department, is doing research in complexity theory - in particular, the properties of an NP-complete problem called Subset Sum.8

The Subset Sum problem is described as follows: given a set of positive integers S and a target sum t, is there a subset of S whose sum is t? It is one of the well-know, so-called "hard" problems in computing. It's actually a very simple problem, and the computer programme to solve it is not extremely complicated. What's hard about it is the running time - all known exact algorithms have running time that is proportional to an exponential function of the number of elements in the set - for worst-case instances of the problem.

Over the years, a large number of combinatorial problems have been shown to be in the same class as Subset Sum - called NP-complete problems. But, depending on how you measure the size of the problem instance, there is evidence that Subset Sum is actually an easier problem than most of the others in its class. The goal of the SubsetSum@Home project is to strengthen the evidence that Subset Sum is an easier hard problem.

Suppose we have a set of n positive whole numbers S whose maximum number is m. We will define the ratio n/m to be the density of the set and denote the sum of all elements in the set as sumS. If you look at the list of sums produced by subsets of S, you notice that very few sums are missing if S is dense enough. In fact, it appears that there is an exact density threshold beyond which no sums between m and half the sum of S will be missing. Preliminary experiments have led to the following hypothesis: A set of positive integers with maximum element m and size n > floor(m/2)+1 has a subset whose sum is t for every t in the range m <t < sumS - m.

So here's where participants can help. So far, the team has not been able to prove the hypothesis above. Participants can send a proof or show where to find one in the research literature, and the project will be done. You can also volunteer your computer as a worker to see how far it is possible to extend the empirical evidence. You will also be helping the team figure out better ways to apply distributed computing to combinatorial problems.

More information is available at http://volunteer.cs.und.edu/subset_sum/progress/index.php
Source: University of North Dakota

Back to Table of contents

Primeur weekly 2013-03-18

Exascale supercomputing

OFC/NFOEC features new research in low-power supercomputing, long-distance 400G data transmission, and simplified multicore fiber nanufacturing ...

Big Bang meets Big Data: South Africa joins ASTRON and IBM to build the foundation for a new era of computing ...

The Cloud

VMware outlines corporate strategy, innovations across software-defined data centre, hybrid Cloud and end-user computing ...

New Open Data Center Alliance White Paper highlights adoption of ODCA Cloud usage models ...

IBM helps Black Point Arts provide faster IT services through City Cloud ...

Desktop Grids

SubSetSum@Home project trying to solve NP-complete problem, known as Subset Sum ...

EuroFlash

451 Research Report: Will Energy Prices Power U.S. Datacentre Growth at Europe's Expense and Short-Circuit Energy Efficiency? ...

ClusterVision completes Top500 class HPC cluster at the University of Paderborn ...

New mathematical techniques allow simulations off-shore wind farms ...

Researchers wanted for The Big Data Challenge ...

PRACE's Open R&D HPC access for industry awarded in a European e-Infrastructure FP7 Project Success Story Competition ...

First Europe-China HPC Conference "Partnership for supercomputing applications in science and industry" ...

PRACE Scientific Conference 2013 to be hosted at ISC'13 in Leipzig ...

PRACE Spring School 2013 to address New and Emerging Technologies - Programming for Accelerators ...

PRACE Summer School 2013 to highlight Frameworks for Scientific Computing on Supercomputers ...

N8 HPC showcased to boost collaboration with industry ...

European Commission selects HP to prpvide mission-critical servers ...

Oracle's "Big Data Readiness Report" for Europe, Middle East and Russia now available ...

USFlash

Fujitsu and NAOJ Begin Operation of Supercomputer for ALMA ...

iVEC@Curtin creates one-stop-shop for IT services ...

DataDirect Networks delivers faster performance than Flash storage, improving trading algorithm development and risk management for financial services companies ...

IBM taps next generation leaders to fuel Watson innovations; USC students aim high in first-ever West Coast Case Competition ...

Quantum computing moves forward ...

Turing Award to the Weizmann Institute's Shafi Goldwasser ...

IBM Software helps Illinois Department of Human Services manage Big Data and transform operations ...