REVIEW 2 cited by
The Easiest Hard Problem: Number Partitioning
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
Number partitioning is one of the classical NP-hard problems of combinatorial optimization. It has applications in areas like public key encryption and task scheduling. The random version of number partitioning has an "easy-hard" phase transition similar to the phase transitions observed in other combinatorial problems like $k$-SAT. In contrast to most other problems, number partitioning is simple enough to obtain detailled and rigorous results on the "hard" and "easy" phase and the transition that separates them. We review the known results on random integer partitioning, give a very simple derivation of the phase transition and discuss the algorithmic implications of both phases.
Forward citations
Cited by 2 Pith papers
-
Green Scheduling with Time-of-Use Tariffs and Machine States: Optimizing Energy Cost via Branch-and-Bound and Bin Packing Strategies
The paper introduces B&B-SPACES, an exact branch-and-bound method with bin-packing heuristics that solves single-machine time-of-use energy scheduling about 100 times faster than prior ILP models on tested benchmarks.
-
A converged architecture for processing 32 Tbps of physics data in real-time at the LHCb experiment
LHCb demonstrates a 32 Tbps trigger-less data-acquisition and fully-GPU filter system with 41 MHz peak HLT1 throughput, the highest real-time software data rate in any physics experiment.
Discussion (0). Continue with ORCID to comment.