Martingale Inequalities and NP-Complete Problems
From MaRDI portal
Publication:5750039
DOI10.1287/moor.12.1.177zbMath0718.60040OpenAlexW2074592422WikidataQ92193545 ScholiaQ92193545MaRDI QIDQ5750039
WanSoo T. Rhee, Michel Talagrand
Publication date: 1987
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.12.1.177
Martingales with discrete parameter (60G42) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Stochastic network models in operations research (90B15)
Related Items
Boundary effects in the traveling salesperson problem ⋮ On the fluctuations of simple matching ⋮ Threshold limits for cover times ⋮ On properties of geometric random problems in the plane ⋮ Probabilistic Analysis of a Vehicle Routing Problem with Time Windows ⋮ Exercising control when confronted by a (Brownian) spider ⋮ The physicist's approach to the travelling salesman problem. II ⋮ Euclidean semi-matchings of random samples ⋮ Average case analysis of bounded space bin packing algorithms ⋮ Some inequalities for bin packing ⋮ Inequalities for bin packing-III ⋮ Probabilistic analysis of a capactiated vehicle routing problem—I ⋮ An asymptotic 98.5\%-effective lower bound on fixed partition policies for the inventory-routing problem ⋮ A concentration inequality for maximum matching size in random graphs1 ⋮ Hoeffding's Inequality for Stopped Martingales and Semi-Markov Processes ⋮ Statistical mechanics methods and phase transitions in optimization problems ⋮ Dual bin packing with items of random sizes ⋮ The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem ⋮ On the k-center problem with many centers ⋮ The Central Limit Theorem and the Law of Large Numbers for Pair-Connectivity in Bernoulli Trees
This page was built for publication: Martingale Inequalities and NP-Complete Problems
