Probabilistic analysis of optimum partitioning

DOI10.2307/3214002MaRDI QIDQ3750704zbMATH OpenOpenAlexFDO

Authors Narendra K. Karmarkar, George S. Lueker, Richard Karp, Andrew Odlyzko

Publication date 1986

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://escholarship.org/uc/item/5gw8j5s6

zbMATH Keywords

combinatorial optimizationoptimum partition problemsecond-moment method

Mathematics Subject Classification ID

Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05)

Recommendations

• Exponentially small bounds on the expected optimum of the partition and subset sum problems
• A note on the average-case behavior of a simple differencing method for partitioning
• scientific article; zbMATH DE number 52589
• Phase transition and finite-size scaling for the integer partitioning problem
• Probabilistic analysis of the number partitioning problem

Cited in

(30)

• Heuristics and exact methods for number partitioning
• A note on the average-case behavior of a simple differencing method for partitioning
• A complete anytime algorithm for number partitioning
• Two-dimensional packing algorithms for layout of disconnected graphs
• Easily searched encodings for number partitioning
• Lattice-based algorithms for number partitioning in the hard phase
• Gaussian discrepancy: a probabilistic relaxation of vector balancing
• Randomized methods for the number partitioning problem
• Optimization strategies for two-mode partitioning
• Phase transition and finite-size scaling for the integer partitioning problem
• Partitions-requirements-matrices as optimal Markov kernels of special stochastic dynamic distance optimal partitioning problems
• Optimal Partitioning of Probability Distributions under General Convex Loss Functions in Selective Assembly
• Making Decisions in Multi Partitioning
• scientific article; zbMATH DE number 4201596 (Why is no real title available?)
• The power of optimization over randomization in designing experiments involving small samples
• Probabilistic analysis of the number partitioning problem
• Exponentially small bounds on the expected optimum of the partition and subset sum problems
• Phase Transition in the Number Partitioning Problem
• Stochastic analysis of partitioning algorithms for matching problems
• Optimal Partitioning of Sequences
• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• Sharp threshold and scaling window for the integer partitioning problem
• LATIN 2004: Theoretical Informatics
• A physicist's approach to number partitioning
• Algorithmic obstructions in the random number partitioning problem
• Average-case matrix discrepancy: satisfiability bounds
• Weaver's discrepancy for Gaussian random vectors
• Probabilistic analysis of a grouping algorithm
• A note on the complexity of a partition algorithm
• On the height of digital trees and related problems

This page was built for publication: Probabilistic analysis of optimum partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3750704)