Log in

Relevant bibliographies by topics / Random combinatorial problems

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers
Reports

Academic literature on the topic 'Random combinatorial problems'

Author: Grafiati

Published: 14 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Random combinatorial problems.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Random combinatorial problems"

1

Coja-Oghlan, Amin, Tobias Kapetanopoulos, and Noela Müller. "The replica symmetric phase of random constraint satisfaction problems." Combinatorics, Probability and Computing 29, no. 3 (December 3, 2019): 346–422. http://dx.doi.org/10.1017/s0963548319000440.

Full text

Abstract:

AbstarctRandom constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark examples for algorithms, and they have been harnessed in probabilistic constructions of combinatorial structures with peculiar features. In an important contribution (Krzakala et al. 2007, Proc. Nat. Acad. Sci.), physicists made several predictions on the precise location and nature of phase transitions in random constraint satisfaction problems. Specifically, they predicted that their satisfiability thresholds are quite generally preceded by several other thresholds that have a substantial impact both combinatorially and computationally. These include the condensation phase transition, where long-range correlations between variables emerge, and the reconstruction threshold. In this paper we prove these physics predictions for a broad class of random constraint satisfaction problems. Additionally, we obtain contiguity results that have implications for Bayesian inference tasks, a subject that has received a great deal of interest recently (e.g. Banks et al. 2016, Proc. 29th COLT).

APA, Harvard, Vancouver, ISO, and other styles

2

Serafini, Paolo. "Combinatorial optimization problems with normal random costs." Operations Research Letters 41, no. 2 (March 2013): 126–33. http://dx.doi.org/10.1016/j.orl.2012.11.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Galbiati, G., and F. Maffioli. "Random pseudo-polynomial algorithms for some combinatorial programming problems." European Journal of Operational Research 58, no. 2 (April 1992): 223–35. http://dx.doi.org/10.1016/0377-2217(92)90209-r.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Leone, Michele, Federico Ricci-Tersenghi, and Riccardo Zecchina. "Phase coexistence and finite-size scaling in random combinatorial problems." Journal of Physics A: Mathematical and General 34, no. 22 (May 24, 2001): 4615–26. http://dx.doi.org/10.1088/0305-4470/34/22/303.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Reznik, A. L., A. A. Soloviev, and A. V. Torgov. "Programs of Recursive Analytical Calculations in Problems of Random Point Images Analysis." Izvestiya of Altai State University, no. 4(114) (September 9, 2020): 112–16. http://dx.doi.org/10.14258/izvasu(2020)4-18.

Full text

Abstract:

The paper discusses an approach to solving complex probabilistic combinatorial problems. The approach is based on the use of specialized software systems for analytical transformations for computing systems. One of the problems associated with the partition of the interval (which arises in the study of the reliability of reading discrete-point fields and digital images) is considered in the paper, and new previously unknown analytical formulas have been successfully obtained. The efficiency of the developed software systems is ensured by two factors: firstly, the development of high-speed specialized recursive-combinatorial algorithms; secondly, the software implementation on high-performance computing clusters using modern programming and development tools (such as C ++ and MPI). Examples of particular solutions to the described problem that are obtained with the help of constructed computer systems are presented. An effective approach to solving complex probabilistic combinatorial problems is demonstrated. For the proposed approach, a computer is not just a powerful "calculator", but is an effective assistant with a wide range of algorithms and programs for complex and branched analytical transformations.

APA, Harvard, Vancouver, ISO, and other styles

6

Kuchinskii, É. Z., and M. V. Sadovskii. "Combinatorial analysis of Feynman diagrams in problems with a Gaussian random field." Journal of Experimental and Theoretical Physics 86, no. 2 (February 1998): 367–74. http://dx.doi.org/10.1134/1.558437.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Liu, Yucheng, and Zhichao Wang. "Some Generalizations of Random Broken and Pick-up Stick Problems." Journal of Physics: Conference Series 2287, no. 1 (June 1, 2022): 012003. http://dx.doi.org/10.1088/1742-6596/2287/1/012003.

Full text

Abstract:

Abstract We consider sticks with random lengths, which are further randomly broken into several pieces. The probability that these sticks can form a polygon is computed in this article. This Broken Pick-up Stick Problem was first asked in [1] and we give a general formula to solve this problem. Besides, we study the probability that any three sticks with independent and uniformly distributed lengths can form a triangle. Our results generalize the famous Spaghetti Problem and the Pick-up Stick Problem in probability. We present a way to transfer these continuous probability problems into discrete problems and apply combinatorial methods to address the discrete version of the problems.

APA, Harvard, Vancouver, ISO, and other styles

8

Bouhmala, Noureddine, and Ole-Christoffer Granmo. "Stochastic Learning for SAT- Encoded Graph Coloring Problems." International Journal of Applied Metaheuristic Computing 1, no. 3 (July 2010): 1–19. http://dx.doi.org/10.4018/jamc.2010070101.

Full text

Abstract:

The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm’s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.

APA, Harvard, Vancouver, ISO, and other styles

9

KNIZHNIK, V. G., A. M. POLYAKOV, and A. B. ZAMOLODCHIKOV. "FRACTAL STRUCTURE OF 2d—QUANTUM GRAVITY." Modern Physics Letters A 03, no. 08 (July 1988): 819–26. http://dx.doi.org/10.1142/s0217732388000982.

Full text

Abstract:

We resolve renormalization problems, indicated in Ref. 1 and find explicit formulae for the spectrum of anomalous dimensions in 2d—quantum gravity. Comparison with combinatorial approximation of random surfaces and its numerical analyses shows complete agreement with all known facts.

APA, Harvard, Vancouver, ISO, and other styles

10

Reznik, A. L., A. A. Solov’ev, and A. V. Torgov. "Program-combinatorial approach to solving problems of error-free readout of random point images." Optoelectronics, Instrumentation and Data Processing 52, no. 2 (March 2016): 121–27. http://dx.doi.org/10.3103/s8756699016020035.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Random combinatorial problems"

1

Meehan, Sean. "On Some Universality Problems in Combinatorial Random Matrix Theory." The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1563381611232149.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

MALATESTA, ENRICO MARIA. "RANDOM COMBINATORIAL OPTIMIZATION PROBLEMS: MEAN FIELD AND FINITE-DIMENSIONAL RESULTS." Doctoral thesis, Università degli Studi di Milano, 2018. http://hdl.handle.net/2434/605056.

Full text

Abstract:

Until the introduction of the first spin glass model by Edwards and Anderson in 1975, the research area of disordered systems has undergone a huge progress, thanks to the introduction of new analytical techniques and numerical tools, as long as the development of novel concepts and ideas. In particular, the rich phenomenology found by the extensive study of mean field spin glass models, not only proved to be the basis for an explanation of many different physical phenomena and permitted to strengthen the traditional relationship between physics and mathematics, but also it allowed physicist to apply those concepts to research areas that were thought to be completely disconnected from physics before. In this thesis I will analyze combinatorial optimization problems, from a physics point of view. In the first two chapters I will review some basic notions of statistical physics of disordered systems, such as random graph theory, the mean-field approximation, spin glasses and combinatorial optimization. The replica method will also be introduced and applied to the Sherrington-Kirkpatrick model, one of the simplest mean-field models of spin-glasses. The second part of the thesis deals with mean-field combinatorial optimization problems. The attention will be focused on finite-size corrections of random integer matching problems (chapter 3) and fractional ones (chapter 4). In chapter 5 I will discuss a very general relation connecting multi-overlaps and the moments of the cavity magnetization distribution. In the third part the Euclidean counterparts of random optimization problems are considered. I will start solving the traveling-salesman-problem (TSP) in one dimension both in its bipartite and monopartite version (chapter 6). In chapter 7 I will discuss the possible optimal solutions of the 2-factor problem. In chapter 8 I will solve the bipartite TSP in two dimensions, in the limit of large number of points. Chapter 9 contain some conclusions.

APA, Harvard, Vancouver, ISO, and other styles

3

Noel, Jonathan A. "Extremal combinatorics, graph limits and computational complexity." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:8743ff27-b5e9-403a-a52a-3d6299792c7b.

Full text

Abstract:

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}^d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Q_m in Q_d. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Q_d of bounded average degree such that G does not contain a copy of Q_m but, for every G' such that G ⊊ G' ⊆ Q_d, the graph G' contains a copy of Q_m. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2^(1-ε)k subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2^{(1+o(1))^ck} for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Q_m in Q_d. That is, we determine the minimum number of edges in a spanning subgraph G of Q_d such that the edges of E(Q_d)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Q_m. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A₀ of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A₀ percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Q_d has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset 𝒱(q,n) consisting of all subspaces of 𝔽_qⁿordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (ε_i)^∞_i=1 tending to zero such that, for all i ≥ 1, every weak ε_i-regular partition of W has at least exp(ε_i^-2/2^{5log∗ε_i^-2}) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤ_p such that any two adjacent vertices are mapped to elements of ℤ_p at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.

APA, Harvard, Vancouver, ISO, and other styles

4

Buckley, Stephen Philip. "Problems in random walks in random environments." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:06a12be2-b831-4c2a-87b1-f0abccfb9b8b.

Full text

Abstract:

Recent years have seen progress in the analysis of the heat kernel for certain reversible random walks in random environments. In particular the work of Barlow(2004) showed that the heat kernel for the random walk on the infinite component of supercritical bond percolation behaves in a Gaussian fashion. This heat kernel control was then used to prove a quenched functional central limit theorem. Following this work several examples have been analysed with anomalous heat kernel behaviour and, in some cases, anomalous scaling limits. We begin by generalizing the first result - looking for sufficient conditions on the geometry of the environment that ensure standard heat kernel upper bounds hold. We prove that these conditions are satisfied with probability one in the case of the random walk on continuum percolation and use the heat kernel bounds to prove an invariance principle. The random walk on dynamic environment is then considered. It is proven that if the environment evolves ergodically and is, in a certain sense, geometrically d-dimensional then standard on diagonal heat kernel bounds hold. Anomalous lower bounds on the heat kernel are also proven - in particular the random conductance model is shown to be "more anomalous" in the dynamic case than the static. Finally, the reflected random walk amongst random conductances is considered. It is shown in one dimension that under the usual scaling, this walk converges to reflected Brownian motion.

APA, Harvard, Vancouver, ISO, and other styles

5

Person, Yury. "Quasi-random hypergraphs and extremal problems for hypergraphs." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2010. http://dx.doi.org/10.18452/16238.

Full text

Abstract:

In dieser Arbeit wird zuerst das Theorem von Chung, Graham und Wilson über quasi-zufällige Graphen zur sogenannten schwachen Quasi-Zufälligkeit für k-uniforme Hypergraphen verallgemeinert und somit eine Reihe äquivalenter Eigenschaften bestimmt. Basierend auf diesen Resultaten werden nichtbipartite Graphen gefunden, welche die Quasi-Zufälligkeit für Graphen ``forcieren''''. Zuvor waren nur bipartite Graphen mit dieser Eigenschaft bekannt. Desweiteren ist ein konzeptionell einfacher Algorithmus zum Verifizieren nicht erfüllbarer zufälliger k-SAT Formeln angegeben. Dann richtet sich der Fokus auf Anwendungen verschiedener Regularitätslemmata für Hypergraphen. Zuerst wird die Menge aller bezeichneten 3-uniformen Hypergraphen auf n Knoten, die keine Kopie des Hypergraphen der Fano Ebene enthalten, studiert. Es wird gezeigt, dass fast jedes Element aus dieser Menge ein bipartiter Hypergraph ist. Dies führt zu einem Algorithmus, der in polynomiell erwarteter Zeit einen zufälligen Fano-freien (und somit einen zufälligen bipartiten 3-uniformen) Hypergraphen richtig färbt. Schließlich wird die folgende extremale Funktion studiert. Es sind r Farben gegeben sowie ein k-uniformer Hypergraph F. Auf wie viele verschiedene Arten kann man die Kanten eines k-uniformen Hypergraphen H färben, so dass keine monochromatische Kopie von F entsteht? Welche Hypergraphen H maximieren die Anzahl erlaubter Kantenfärbungen? Hier wird ein strukturelles Resultat für eine natürliche Klasse von Hypergraphen bewiesen. Es wird für viele Hypergraphen F, deren extremaler Hypergraph bekannt ist, gezeigt, dass im Falle von zwei oder drei Farben die extremalen Hypergraphen die oben beschriebene Funktion maximieren, während für vier oder mehr Farben andere Hypergraphen mehr Kantenfärbungen zulassen.
This thesis presents first one possible generalization of the result of Chung, Graham and Wilson to k-uniform hypergraphs, and studies the so-called weak quasi-randomness. As applications we obtain a simple strong refutation algorithm for random sparse k-SAT formulas and we identify first non-bipartite forcing pairs for quasi-random graphs. Our focus then shifts from the study of quasi-random objects to applications of different versions of the hypergraph regularity lemmas; all these versions assert decompositions of hypergraphs into constantly many quasi-random parts, where the meaning of ``quasi-random'''' takes different contexts in different situations. We study the family of hypergraphs not containing the hypergraph of the Fano plane as a subhypergraph, and show that almost all members of this family are bipartite. As a consequence an algorithm for coloring bipartite 3-uniform hypergraphs with average polynomial running time is given. Then the following combinatorial extremal problem is considered. Suppose one is given r colors and a fixed hypergraph F. The question is: In at most how many ways can one color the hyperedges of a hypergraph H on n vertices such that no monochromatic copy of F is created? What are the extremal hypergraphs for this function? Here a structural result for a natural family of hypergraphs F is proven. For some special classes of hypergraphs we show that their extremal hypergraphs (for large n) maximize the number of edge colorings for 2 and 3 colors, while for at least 4 colors other hypergraphs are optimal.

APA, Harvard, Vancouver, ISO, and other styles

6

Creed, Patrick John. "Counting and sampling problems on Eulerian graphs." Thesis, University of Edinburgh, 2010. http://hdl.handle.net/1842/4759.

Full text

Abstract:

In this thesis we consider two sets of combinatorial structures defined on an Eulerian graph: the Eulerian orientations and Euler tours. We are interested in the computational problems of counting (computing the number of elements in the set) and sampling (generating a random element of the set). Specifically, we are interested in the question of when there exists an efficient algorithm for counting or sampling the elements of either set. The Eulerian orientations of a number of classes of planar lattices are of practical significance as they correspond to configurations of certain models studied in statistical physics. In 1992 Mihail and Winkler showed that counting Eulerian orientations of a general Eulerian graph is #P-complete and demonstrated that the problem of sampling an Eulerian orientation can be reduced to the tractable problem of sampling a perfect matching of a bipartite graph. We present a proof that this problem remains #Pcomplete when the input is restricted to being a planar graph, and analyse a natural algorithm for generating random Eulerian orientations of one of the afore-mentioned planar lattices. Moreover, we make some progress towards classifying the range of planar graphs on which this algorithm is rapidly mixing by exhibiting an infinite class of planar graphs for which the algorithm will always take an exponential amount of time to converge. The problem of counting the Euler tours of undirected graphs has proven to be less amenable to analysis than that of Eulerian orientations. Although it has been known for many years that the number of Euler tours of any directed graph can be computed in polynomial time, until recently very little was known about the complexity of counting Euler tours of an undirected graph. Brightwell and Winkler showed that this problem is #P-complete in 2005 and, apart from a few very simple examples, e.g., series-parellel graphs, there are no known tractable cases, nor are there any good reasons to believe the problem to be intractable. Moreover, despite several unsuccessful attempts, there has been no progress made on the question of approximability. Indeed, this problem was considered to be one of the more difficult open problems in approximate counting since long before the complexity of exact counting was resolved. By considering a randomised input model, we are able to show that a very simple algorithm can sample or approximately count the Euler tours of almost every d-in/d-out directed graph in expected polynomial time. Then, we present some partial results towards showing that this algorithm can be used to sample or approximately count the Euler tours of almost every 2d-regular graph in expected polynomial time. We also provide some empirical evidence to support the unproven conjecture required to obtain this result. As a sideresult of this work, we obtain an asymptotic characterisation of the distribution of the number of Eulerian orientations of a random 2d-regular graph.

APA, Harvard, Vancouver, ISO, and other styles

7

Coregliano, Leonardo Nagami. "Flag algebras and tournaments." Universidade de São Paulo, 2015. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12082015-093248/.

Full text

Abstract:

Alexander A. Razborov (2007) developed the theory of flag algebras to compute the minimum asymptotic density of triangles in a graph as a function of its edge density. The theory of flag algebras, however, can be used to study the asymptotic density of several combinatorial objects. In this dissertation, we present two original results obtained in the theory of tournaments through application of flag algebra proof techniques. The first result concerns minimization of the asymptotic density of transitive tournaments in a sequence of tournaments, which we prove to occur if and only if the sequence is quasi-random. As a byproduct, we also obtain new quasi-random characterizations and several other flag algebra elements whose density is minimized if and only if the sequence is quasi-random. The second result concerns a class of equivalent properties of a sequence of tournaments that we call quasi-carousel properties and that, in a similar fashion as quasi-random properties, force the sequence to converge to a specific limit homomorphism. Several quasi-carousel properties, when compared to quasi-random properties, suggest that quasi-random sequences and quasi-carousel sequences are the furthest possible from each other within the class of almost balanced sequences.
Alexander A. Razborov (2007) desenvolveu a teoria de álgebras de flags para calcular a densidade assintótica mínima de triângulos em um grafo em função de sua densidade de arestas. A teoria das álgebras de flags, contudo, pode ser usada para estudar densidades assintóticas de diversos objetos combinatórios. Nesta dissertação, apresentamos dois resultados originais obtidos na teoria de torneios através de técnicas de demonstração de álgebras de flags. O primeiro resultado compreende a minimização da densidade assintótica de torneios transitivos em uma sequência de torneios, a qual provamos ocorrer se e somente se a sequência é quase aleatória. Como subprodutos, obtemos também novas caracterizações de quase aleatoriedade e diversos outros elementos da álgebra de flags cuja densidade é minimizada se e somente se a sequência é quase aleatória. O segundo resultado compreende uma classe de propriedades equivalentes sobre uma sequência de torneios que chamamos de propriedades quase carrossel e que, de uma forma similar às propriedades quase aleatórias, forçam que a sequência convirja para um homomorfismo limite específico. Várias propriedades quase carrossel, quando comparadas às propriedades quase aleatórias, sugerem que sequências quase aleatórias e sequências quase carrossel estão o mais distantes possível umas das outras na classe de sequências quase balanceadas.

APA, Harvard, Vancouver, ISO, and other styles

8

Law, Hiu-Fai. "Trees and graphs : congestion, polynomials and reconstruction." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:54190b51-cd9d-489e-a79e-82ecdf15b4c5.

Full text

Abstract:

Spanning tree congestion was defined by Ostrovskii (2004) as a measure of how well a network can perform if only minimal connection can be maintained. We compute the parameter for several families of graphs. In particular, by partitioning a hypercube into pieces with almost optimal edge-boundaries, we give tight estimates of the parameter thereby disproving a conjecture of Hruska (2008). For a typical random graph, the parameter exhibits a zigzag behaviour reflecting the feature that it is not monotone in the number of edges. This motivates the study of the most congested graphs where we show that any graph is close to a graph with small congestion. Next, we enumerate independent sets. Using the independent set polynomial, we compute the extrema of averages in trees and graphs. Furthermore, we consider inverse problems among trees and resolve a conjecture of Wagner (2009). A result in a more general setting is also proved which answers a question of Alon, Haber and Krivelevich (2011). After briefly considering polynomial invariants of general graphs, we specialize into trees. Three levels of tree distinguishing power are exhibited. We show that polynomials which do not distinguish rooted trees define typically exponentially large equivalence classes. On the other hand, we prove that the rooted Ising polynomial distinguishes rooted trees and that the Negami polynomial determines the subtree polynomial, strengthening results of Bollobás and Riordan (2000) and Martin, Morin and Wagner (2008). The top level consists of the chromatic symmetric function and it is proved to be a complete invariant for caterpillars.

APA, Harvard, Vancouver, ISO, and other styles

9

Demopoulos, Demetrios D. "Probabilistic phenomena in random combinatorial problems." Thesis, 2003. http://hdl.handle.net/1911/17587.

Full text

Abstract:

This is an experimental investigation of three combinatorial problems. I examined the average-case complexity of random 3-SAT and of 3-Colorability of random graphs, and the satisfiability of random 1-3-HornSAT. All these problems, not only are interesting for their own sake, but also are of great practical importance since many other problems in computer science, engineering and other fields can be reduced to these. We systematically explored a large part of the problems' space, varying the size and the constrainedness of the instances, as well as the tools we used to solve them. We observed new phase transitions from polynomial to exponential complexity for random 3-SAT. A similar picture emerged for 3-Colorability. These experimental observations are important for understanding the inherent computational complexity of the problems. In the case of random 1-3-HornSAT, our findings suggest that there is a threshold at which the satisfiability changes from 1 to 0.

APA, Harvard, Vancouver, ISO, and other styles

10

Theran, Louis Simon. "Problems in Generic Combinatorial Rigidity: Sparsity, Sliders, and Emergence of Components." 2010. https://scholarworks.umass.edu/open_access_dissertations/316.

Full text

Abstract:

Rigidity theory deals in problems of the following form: given a structure defined by geometric constraints on a set of objects, what information about its geometric behavior is implied by the underlying combinatorial structure. The most well-studied class of structures is the bar-joint framework, which is made of fixed-length bars connected by universal joints with full rotational degrees of freedom; the allowed motions preserve the lengths and connectivity of the bars, and a framework is rigid if the only allowed motions are trivial motions of Euclidean space. A remarkable theorem of Maxwell-Laman says that rigidity of generic bar-joint frameworks depends only on the graph that has as its edges the bars and as its vertices the joints. We generalize the "degree of freedom counts that appear in the Maxwell-Laman theorem to the very general setting of (k,l)-sparse and (k,l)-graded sparse hypergraphs. We characterize these in terms of their graph-graph theoretic and matroidal properties. For the fundamental algorithmic problems Decision, Extraction, Components, and Decomposition, we give efficient, implementable pebble game algorithms for all the (k,l)-sparse and (k,l)-graded-sparse families of hypergraphs we study. We then prove that all the matroids arising from (k,l)-sparse are linearly representable by matrices with a certain "natural" structure that captures the incidence structure of the hypergraph and the sparsity parameters k and l. Building on the combinatorial and linear theory discussed above, we introduce a new rigidity model: slider-pinning rigidity. This is an elaboration of the planar bar-joint model to include sliders, which constrain a vertex to move on a specific line. We prove the analogue of the Maxwell-Laman Theorem for slider pinning, using, as a lemma, a new proof of Whiteley's Parallel Redrawing Theorem. We conclude by studying the emergence of non-trivial rigid substructures in generic planar frameworks given by Erdos-Renyi random graphs. We prove that there is a sharp threshold for such substructures to emerge, and that, when they do, they are all linear size. This is consistent with experimental and simulation-based work done in the physics community on the formation of certain glasses.

APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Random combinatorial problems"

1

Yukich, Joseph. Probability theory of classical Euclidean optimization problems. Berlin: Springer, 1998.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

2

Chandra, Chekuri, and International Workshop on Randomization and Computation (9th : 2005 : Berkeley, Calif.), eds. Approximation, randomization, and combinatorial optimization: Algorithms and techniques : 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005, and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005 : proceedings. Berlin: Springer, 2005.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

1950-, Díaz J., and International Workshop on Randomization and Computation (10th : 2006 : Barcelona, Spain), eds. Approximation, randomization and combinatorial optimization: Algorithms and techniques : 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006, and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30, 2006 : proceedings. Berlin: Springer, 2006.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Spencer, Joel H. Asymptopia. Providence, Rhode Island: American Mathematical Society, 2014.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (7th 2004 Cambridge, Mass.). Approximation, randomization, and combinatorial optimization : algorithms and techniques: 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004 : proceedings. Berlin: Springer, 2004.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

6

International Workshop on Randomization and Approximation Techniques in Computer Science (3rd 1999 Berkeley, Calif.). Randomization, approximation, and combinatorial optimization: Algorithms and techniques : Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX '99, Berkeley, CA, August 8-11, 1999, proceedings. Berlin: Springer, 1999.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

7

Sanjeev, Arora, and International Workshop on Randomization and Approximation Techniques in Computer Science (7th : 2003 : Princeton, N.J.), eds. Approximation, randomization, and combinatorial optimization: Algorithms and techniques : 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003, and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003 : proceedings. Berlin: Springer, 2003.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

8

Michel, Goemans, and International Workshop on Randomization and Approximation Techniques in Computer Science (5th : 2001 : Berkeley, Calif.), eds. Approximation, randomization, and combinatorial optimization: Algorithms and techniques : 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Berkeley, CA, USA, August 18-20, 2001, proceedings. New York: Springer, 2001.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

9

Paliy, Irina. Probability theory and mathematical statistics. ru: INFRA-M Academic Publishing LLC., 2021. http://dx.doi.org/10.12737/1065828.

Full text

Abstract:

The tutorial is an introductory course in probability theory and mathematical statistics. Elements of combinatorics, basic concepts and theorems of probability theory, discrete random variables, continuous random variables, some limit theorems, one-dimensional and two-dimensional samples, point and interval estimation of parameters of the general population, testing of statistical hypotheses, elements of queuing theory are considered. The presentation of the theoretical material is accompanied by a large number of detailed examples of problem solving. For students of technical and economic fields of study and specialties, studying under the bachelor's and specialty programs.

APA, Harvard, Vancouver, ISO, and other styles

10

Paliy, Irina, V. A. Dalinger, and B. S. Dobronec. Probability theory and mathematical statistics. ru: INFRA-M Academic Publishing LLC., 2023. http://dx.doi.org/10.12737/1859126.

Full text

Abstract:

The textbook is an introductory course in probability theory and mathematical statistics. Elements of combinatorics, basic concepts and theorems of probability theory, discrete random variables, continuous random variables, some limit theorems, one-dimensional and two-dimensional samples, point and interval estimation of the parameters of the general population, verification of statistical hypotheses, elements of queuing theory are considered. The presentation of the theoretical material is accompanied by a large number of detailed examples of problem solving. For students of technical and economic areas of training and specialties, studying under bachelor's and specialty programs.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Book chapters on the topic "Random combinatorial problems"

1

Shen, Yilin, Xiang Li, and My T. Thai. "Approximation Algorithms for Optimization Problems in Random Power-Law Graphs." In Combinatorial Optimization and Applications, 343–55. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-12691-3_26.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Welsh, Dominic. "Percolation and the Random Cluster Model: Combinatorial and Algorithmic Problems." In Algorithms and Combinatorics, 166–94. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/978-3-662-12788-9_5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Stamatatos, Efstathios, and Kostas Stergiou. "Learning How to Propagate Using Random Probing." In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 263–78. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-01929-6_20.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Pferschy, Ulrich. "The random linear bottleneck assignment problem." In Integer Programming and Combinatorial Optimization, 145–56. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-59408-6_48.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Bierwirth, Christian, Dirk Christian Mattfeld, and Jean-Paul Watson. "Landscape Regularity and Random Walks for the Job-Shop Scheduling Problem." In Evolutionary Computation in Combinatorial Optimization, 21–30. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24652-7_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Heilig, Leonard, Eduardo Lalla-Ruiz, and Stefan Voß. "A Biased Random-Key Genetic Algorithm for the Cloud Resource Management Problem." In Evolutionary Computation in Combinatorial Optimization, 1–12. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-16468-7_1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Frieze, Alan, and Michael Molloy. "The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems." In Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques, 275–89. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-45198-3_24.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Baltz, Andreas, Tomasz Schoen, and Anand Srivastav. "On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation." In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 192–201. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-44666-4_22.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Guionnet, Alice. "Heavy Tailed Random Matrices: How They Differ from the GOE, and Open Problems." In Computation and Combinatorics in Dynamics, Stochastics and Control, 415–27. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-01593-0_15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Bassino, Frédérique, Tsinjo Rakotoarimalala, and Andrea Sportiello. "The complexity of the Multiple Pattern Matching Problem for random strings." In 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 40–53. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2018. http://dx.doi.org/10.1137/1.9781611975062.5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Random combinatorial problems"

1

De Moraes, Matheus Bernardelli, and Guilherme Palermo Coelho. "A Random Forest-Assisted Decomposition-Based Evolutionary Algorithm for Multi-Objective Combinatorial Optimization Problems." In 2022 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2022. http://dx.doi.org/10.1109/cec55065.2022.9870412.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hemmi, David. "Stochastic Constraint Programming." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/751.

Full text

Abstract:

Combinatorial optimisation problems often contain uncertainty that has to be taken into account to pro- duce realistic solutions. One way of describing the uncertainty is using scenarios, where each sce- nario describes different potential sets of problem parameters based on random distributions or his- torical data. While efficient algorithmic techniques exist for specific problem classes such as linear pro- grams, there are very few approaches that can han- dle general Constraint Programming formulations with uncertainty. The goal of my PhD is to develop generic methods for solving stochastic combina- torial optimisation problems formulated in a Con- straint Programming framework.

APA, Harvard, Vancouver, ISO, and other styles

3

Yokoyama, Soichiro, Ikuo Suzuki, Masahito Yamamoto, and Masashi Furukawa. "A New Heuristic for Traveling Salesman Problem Based on LCO." In ASME/ISCIE 2012 International Symposium on Flexible Automation. American Society of Mechanical Engineers, 2012. http://dx.doi.org/10.1115/isfa2012-7227.

Full text

Abstract:

The Traveling Salesman Problem (TSP) is one of the most well known combinatorial optimization problem and has wide range of application. Since the TSP is NP-hard, many heuristics for the TSP have been developed. This study proposes a new heuristic for the TSP based on one of these heuristics named Local Clustering Optimization (LCO). LCO is a metaheuristic proposed by Furukawa at el. to give an accurate solution for large scale problems in a reasonable time. However, conventional LCO-based heuristics for the TSP is not suited to solving asymmetric instances. The proposed method iteratively adopts tour construction heuristics such as nearest neighbor and random insertion to get an accurate solution more efficiently for the both asymmetric and symmetric TSP. The proposed method and other heuristics are applied to benchmark instances from TSPLIB and randomly generated instances. The experiment shows the proposed method is superior to conventional LCO in terms of accuracy of the solution. However, the proposed method is inefficient for instances which are not close to Euclidean due to the same property of insertion heuristic.

APA, Harvard, Vancouver, ISO, and other styles

4

Li, Chu-Min, Zhenxing Xu, Jordi Coll, Felip Manyà, Djamal Habet, and Kun He. "Combining Clause Learning and Branch and Bound for MaxSAT (Extended Abstract)." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/739.

Full text

Abstract:

Branch and Bound (BnB) has been successfully used to solve many combinatorial optimization problems. However, BnB MaxSAT solvers perform poorly when solving real-world and academic optimization problems. They are only competitive for random and some crafted instances. Thus, it is a prevailing opinion in the community that BnB is not really useful for practical MaxSAT solving. We refute this opinion by presenting a new BnB MaxSAT solver, called MaxCDCL, which combines clause learning and an efficient bounding procedure. MaxCDCL is among the top 5 out of a total of 15 exact solvers that participated in the 2020 MaxSAT Evaluation, solving several instances that other solvers cannot solve. Furthermore, MaxCDCL solves the highest number of instances from different MaxSAT Evaluations when combined with the best existing solvers.

APA, Harvard, Vancouver, ISO, and other styles

5

Ishihata, Masakazu, and Takanori Maehara. "Exact Bernoulli Scan Statistics using Binary Decision Diagrams." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/795.

Full text

Abstract:

In combinatorial statistics, we are interested in a statistical test of combinatorial correlation, i.e., existence a subset from an underlying combinatorial structure such that the observation is large on the subset. The combinatorial scan statistics has been proposed for such a statistical test; however, it is not commonly used in practice because of its high computational cost. In this study, we restrict our attention to the case that the number of data points is moderately small (e.g., 50), the outcome is binary, and the underlying combinatorial structure is represented by a zero-suppressed binary decision diagram (ZDD), and consider the problem of computing the p-value of the combinatorial scan statistics exactly. First, we prove that this problem is a #P-hard problem. Then, we propose a practical algorithm that solves the problem. Here, the algorithm constructs a binary decision diagram (BDD) for a set of realizations of the random variables by a dynamic programming on the ZDD, and computes the p-value by a dynamic programming on the BDD. We conducted experiments to evaluate the performance of the proposed algorithm using real-world datasets.

APA, Harvard, Vancouver, ISO, and other styles

6

Fujita, Kikuo, Shinsuke Akagi, Kiyotaka Yoshida, and Noriyasu Hirokawa. "Genetic Algorithm Based Optimal Planning Method of Energy Plant Configurations." In ASME 1996 Design Engineering Technical Conferences and Computers in Engineering Conference. American Society of Mechanical Engineers, 1996. http://dx.doi.org/10.1115/96-detc/dac-1464.

Full text

Abstract:

Abstract A genetic algorithm based optimization method is proposed for the planning problem of energy plant configurations. In such a planning problem, a plant configuration, i.e., types, models, and numbers of equipment, is determined so as to satisfy required energy demand conditions and to minimize the sum of plant facility cost and input energy cost. This is a combinatorial optimization problem similar to the knapsack problem, which is hard to find an optimal configuration for due to the huge number of alternatives. In this paper, we apply a genetic algorithm to such an optimal planning problem by representing a plant configuration with bit vectors and by arranging cost functions so as to keep search performance superior against the deceptive problem. The method is implemented on a symmetric shared-memory, multi-CPU workstation, where almost linear speedup is accomplished. Its performance is demonstrated by computational examples of a cogeneration plant and comparison results with a random search and a simulated annealing method.

APA, Harvard, Vancouver, ISO, and other styles

7

Cai, Shaowei, Wenying Hou, Jinkun Lin, and Yuanjie Li. "Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/196.

Full text

Abstract:

The minimum weight vertex cover (MWVC) problem is an important combinatorial optimization problem with various real-world applications. Due to its NP hardness, most works on solving MWVC focus on heuristic algorithms that can return a good quality solution in reasonable time. In this work, we propose two dynamic strategies that adjust the behavior of the algorithm during search, which are used to improve a state of the art local search for MWVC named FastWVC, resulting in two local search algorithms called DynWVC1 and DynWVC2. Previous MWVC algorithms are evaluated on graphs with random or hand crafted weights. In this work, we evaluate the algorithms on the vertex weighted graphs that obtained from an important real world problem, the map labeling problem. Experiments show that our algorithm obtains better results than previous algorithms for MWVC and maximum weight independent set (MWIS) on these real world instances. We also test our algorithms on massive graphs studied in previous works, and show significant improvements there.

APA, Harvard, Vancouver, ISO, and other styles

8

Rakotoarison, Herilalaina, Marc Schoenauer, and Michèle Sebag. "Automated Machine Learning with Monte-Carlo Tree Search." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/457.

Full text

Abstract:

The AutoML approach aims to deliver peak performance from a machine learning portfolio on the dataset at hand. A Monte-Carlo Tree Search Algorithm Selection and Configuration (Mosaic) approach is presented to tackle this mixed (combinatorial and continuous) expensive optimization problem on the structured search space of ML pipelines. Extensive lesion studies are conducted to independently assess and compare: i) the optimization processes based on Bayesian Optimization or Monte Carlo Tree Search (MCTS); ii) its warm-start initialization based on meta-features or random runs; iii) the ensembling of the solutions gathered along the search. Mosaic is assessed on the OpenML 100 benchmark and the Scikit-learn portfolio, with statistically significant gains over AutoSkLearn, winner of all former AutoML challenges.

APA, Harvard, Vancouver, ISO, and other styles

9

Buermann, Jan, and Jie Zhang. "Multi-Robot Adversarial Patrolling Strategies via Lattice Paths." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/582.

Full text

Abstract:

In full-knowledge multi-robot adversarial patrolling, a group of robots have to detect an adversary who knows the robots' strategy. The adversary can easily take advantage of any deterministic patrolling strategy, which necessitates the employment of a randomised strategy. While the Markov decision process has been the dominant methodology in computing the penetration detection probabilities, we apply enumerative combinatorics to characterise the penetration detection probabilities. It allows us to provide the closed formulae of these probabilities and facilitates characterising optimal random defence strategies. Comparing to iteratively updating the Markov transition matrices, our methods significantly reduces the time and space complexity of solving the problem. We use this method to tackle four penetration configurations.

APA, Harvard, Vancouver, ISO, and other styles

10

Pucheta, Martín A., Nicolás E. Ulrich, and Alberto Cardona. "Combined Graph Layout Algorithms for Automated Sketching of Kinematic Chains." In ASME 2012 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2012. http://dx.doi.org/10.1115/detc2012-70665.

Full text

Abstract:

The graph layout problem arises frequently in the conceptual stage of mechanism design, specially in the enumeration process where a large number of topological solutions must be analyzed. Two main objectives of graph layout are the avoidance or minimization of edge crossings and the aesthetics. Edge crossings cannot be always avoided by force-directed algorithms since they reach a minimum of the energy in dependence with the initial position of the vertices, often randomly generated. Combinatorial algorithms based on the properties of the graph representation of the kinematic chain can be used to find an adequate initial position of the vertices with minimal edge crossings. To select an initial layout, the minimal independent loops of the graph can be drawn as circles followed by arcs, in all forms. The computational cost of this algorithm grows as factorial with the number of independent loops. This paper presents a combination of two algorithms: a combinatorial algorithm followed by a force-directed algorithm based on spring repulsion and electrical attraction, including a new concept of vertex-to-edge repulsion to improve aesthetics and minimize crossings. Atlases of graphs of complex kinematic chains are used to validate the results. The layouts obtained have good quality in terms of minimization of edge crossings and maximization of aesthetic characteristics.

APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Random combinatorial problems"

1

Denley, Tristan, Talmage J. Reid, and Haidong Wu. Applications of Random Methods in Combinatories and Scheduling Problems. Fort Belvoir, VA: Defense Technical Information Center, December 2002. http://dx.doi.org/10.21236/ada408961.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!