Probability-boosting technique for combinatorial optimization [PDF]
PeerJ Computer ScienceIn many combinatorial optimization problems we want a particular set of k out of n items with some certain properties (or constraints). These properties may involve the k items. In the worst case a deterministic algorithm must scan n−k items in the set to verify the k items.
Sanpawat Kantabutra
openaire +4 more sources
Near-medians that avoid the corners; a combinatorial probability approach. [PDF]
BMC Genomics, 2014 The breakpoint median for a set of k ≥ 3 random genomes tends to approach (any) one of these genomes ("corners") as genome length increases, although there are diminishing proportion of medians equidistant from all k ("medians in the middle"). Algorithms are likely to miss the latter, and this has consequences for the general case where input genomes ...
Larlee C, Zheng C, Sankoff D.
europepmc +4 more sources
SamplingDesign: RNA design via continuous optimization with coupled variables and Monte-Carlo sampling. [PDF]
Nat CommunRNA design aims to find a sequence that can fold into a target secondary structure. It can create artificial RNA molecules for specific functions, with wide applications in medicine.
Tang WY +4 more
europepmc +2 more sources
Extremal Probability Bounds in Combinatorial Optimization [PDF]
SIAM Journal on Optimization, 2021 In this paper, we compute the tightest possible bounds on the probability that the optimal value of a combinatorial optimization problem in maximization form with a random objective exceeds a given number, assuming only knowledge of the marginal distributions of the objective coefficient vector.
Divya Padmanabhan +3 more
openaire +5 more sources
Volume Laws for Boxed Plane Partitions and Area Laws for Ferrers Diagrams [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 We asymptotically analyse the volume random variables of general, symmetric and cyclically symmetric plane partitions fitting inside a box. We consider the respective symmetry class equipped with the uniform distribution.
Uwe Schwerdtfeger
doaj +1 more source
Exactly Solvable Balanced Tenable Urns with Random Entries via the Analytic Methodology [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 This paper develops an analytic theory for the study of some Pólya urns with random rules. The idea is to extend the isomorphism theorem in Flajolet et al.
Basile Morcrette, Hosam M. Mahmoud
doaj +1 more source
The Size of the rth Smallest Component in Decomposable Structures with a Restricted Pattern [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 In our previous work [paper1], we derived an asymptotic expression for the probability that a random decomposable combinatorial structure of size n in the \exp -\log class has a given restricted pattern.
Li Dong, Zhicheng Gao, Daniel Panario
doaj +1 more source
Scientific Creativity: Discovery and Invention as Combinatorial
Frontiers in Psychology, 2021 Although scientific creativity has often been described as combinatorial, the description is usually insufficiently formulated to count as a precise scientific explanation.
Dean Keith Simonton
doaj +1 more source
A Combinatorial Model for Determining Information Loss in Organizational and Technical Systems
Mathematics, 2022 A combinatorial model is proposed for determining the probability and information losses in an organizational and technical system (OTS) under destructive external influences.
Alexey V. Yakovlev +3 more
doaj +1 more source
Possibilities determine the combinatorial structure of probability polytopes [PDF]
Journal of Mathematical Psychology, 2016 We study the set of no-signalling empirical models on a measurement scenario, and show that the combinatorial structure of the no-signalling polytope is completely determined by the possibilistic information given by the support of the models. This is a special case of a general result which applies to all polytopes presented in a standard form, given ...
Abramsky, S +4 more
openaire +4 more sources