20 results
Search Results
2. Simple, Fast and Deterministic Gossip and Rumor Spreading.
- Author
-
HAEUPLER, BERNHARD
- Subjects
MATHEMATICAL programming ,ROBUST control ,ALGORITHMS ,SYSTEMS design ,INFORMATION dissemination - Abstract
We study gossip algorithms for the rumor spreading problem, which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as message efficient, simple, and robust solutions to the rumor spreading problem. A long series of papers analyzed the performance of uniform random gossip in which nodes repeatedly call a random neighbor to exchange all rumors with. A main result of this investigation was that uniform gossip completes in O(log n/Φ) rounds where Φ is the conductance of the network. Nonuniform random gossip schemes were devised to allow efficient rumor spreading in networks with bottlenecks. In particular, [Censor-Hillel et al., STOC'12] gave an O(log³ n) algorithm to solve the 1-local broadcast problem in which each node wants to exchange rumors locally with its 1-neighborhood. By repeatedly applying this protocol, one can solve the global rumor spreading quickly for all networks with small diameter, independently of the conductance. All these algorithms are inherently randomized in their design and analysis. A parallel research direction has been to reduce and determine the amount of randomness needed for efficient rumor spreading. This has been done via lower bounds for restricted models and by designing gossip algorithms with a reduced need for randomness, for instance, by using pseudorandom generators with short random seeds. The general intuition and consensus of these results has been that randomization plays a important role in effectively spreading rumors and that at least a polylogarithmic number of random bit are crucially needed. In this article improves over the state of the art in several ways by presenting a deterministic gossip algorithm that solves the the k-local broadcast problem in 2(k + log
2 n) log2 n rounds. Besides being the first efficient deterministic solution to the rumor spreading problem this algorithm is interesting in many aspects: It is simpler, more natural, more robust, and faster than its randomized pendant and guarantees success with certainty instead of with high probability. Its analysis is furthermore simple, self-contained, and fundamentally different from prior works. [ABSTRACT FROM AUTHOR]- Published
- 2015
- Full Text
- View/download PDF
3. Algorithm 457 Finding All Cliques of an Undirected Graph [ H ].
- Author
-
Bron, Coen, Kerbosch, Joep, Roy, Mohit Kumar, Lawrence, E. E., and Williamson, Hugh
- Subjects
ALGORITHMS ,GRAPH theory ,BRANCH & bound algorithms ,MATHEMATICAL programming ,ALGEBRA ,MATHEMATICS - Abstract
The article reports on finding all subgraphs of an undirected graph [H]. A maximal complete subgraph is also called clique which refers to a complete subgraph that is not included in any other complete subgraph. According to the authors, a research paper was released wherein descriptions of techniques to find maximal complete subgraphs are provided. The authors discussed two algorithms using a branch-and-bound technique so that there will be no clique. The first algorithm produces cliques in lexicographic order while the second is derived from the first algorithm.
- Published
- 1973
- Full Text
- View/download PDF
4. Improving Programs by the Introduction of Recursion.
- Author
-
Bird, R. S.
- Subjects
RECURSIVE functions ,PROGRAM transformation ,ALGORITHMS ,MATHEMATICAL transformations ,MATHEMATICAL programming ,TRANSFORMATION groups ,SIMILARITY transformations ,MATHEMATICAL optimization ,NONLINEAR programming - Abstract
A new technique of program transformation, called "recursion introduction," is described and applied to two algorithms which solve pattern matching problems. By using recursion introduction, algorithms which manipulate a stack are first translated into recursive algorithms in which no stack operations occur. These algorithms are then subjected to a second transformation, a method of recursion elimination called "tabulation," to produce programs with a very efficient running time. In particular, it is shown how the fast linear pattern matching algorithm of Knuth, Morris, and Pratt can be derived in a few steps from a simple nonlinear stack algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1977
- Full Text
- View/download PDF
5. Further Evidence for the Analysis of Algorithms for the Zero-One Programming Problem.
- Author
-
Proll, L. G.
- Subjects
ALGORITHMS ,DYNAMIC programming ,LINEAR programming ,MATHEMATICAL programming ,PRODUCTION scheduling ,VECTOR analysis - Abstract
The purpose of this note is to report computational experience additional to that recently summarized by Gue et al., with two algorithms for the zero-one linear programming problem. An error in Gue's paper is corrected. The utility of one of the algorithms as a suboptimizer is indicated. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
6. An Updated Survey of GA-Based Multiobjective Optimization Techniques.
- Author
-
Coello Coello, Carlos A.
- Subjects
- *
MATHEMATICAL optimization , *MATHEMATICAL programming , *ALGORITHMS , *ARTIFICIAL intelligence , *GENETIC algorithms , *RESEARCH - Abstract
After using evolutionary techniques for single-objective optimization during more than two decades, the incorporation of more than one objective in the fitness function has finally become a popular area of research. As a consequence, many new evolutionary-based approaches and variations of existing techniques have recently been published in the technical literature. The purpose of this paper is to summarize and organize the information on these current approaches, emphasizing the importance of analyzing the operations research techniques in which most of them are based, in an attempt to motivate researchers to look into these mathematical programming approaches for new ways of exploiting the search capabilities of evolutionary algorithms. Furthermore, a summary of the main algorithms behind these approaches is provided, together with a brief criticism that includes their advantages and disadvantages, degree of applicability, and some known applications. Finally, future trends in this area and some possible paths for further research are also addressed. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
7. Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems.
- Author
-
BARUAH, SANJOY, BONIFACI, VINCENZO, D'ANGELO, GIANLORENZO, HAOHAN LI, MARCHETTI-SPACCAMELA, ALBERTO, VAN DER STER, SUZANNE, and STOUGIE, LEEN
- Subjects
SPORADIC groups (Mathematics) ,ALGORITHMS ,MATHEMATICS ,ALGEBRA ,MATHEMATICAL programming - Abstract
Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the rest of the functionality is non-safety-critical and does not need to be certified, or is certified to lower levels of assurance. The certification-cognizant runtime scheduling of such mixedcriticality systems is considered. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is presented: this algorithm can schedule systems for which any number of criticality levels are defined. Efficient implementations of EDF-VD, as well as associated schedulability tests for determining whether a task system can be correctly scheduled using EDF-VD, are presented. For up to 13 criticality levels, analyses of EDF-VD, based on metrics such as processor speedup factor and utilization bounds, are derived, and conditions under which EDF-VD is optimal with respect to these metrics are identified. Finally, two extensions of EDF-VD are discussed that enhance its applicability. The extensions are aimed at scheduling a wider range of task sets, while preserving the favorable worst-case resource usage guarantees of the basic algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
8. A Survey of Resource Directive Decomposition in Mathematical Programming.
- Author
-
Molina, Francisco Walter
- Subjects
- *
MATHEMATICAL programming , *ALGORITHMS , *DECOMPOSITION method , *SYSTEM analysis , *OPERATIONS research , *PROGRAM transformation , *COMPUTER science - Abstract
Because of the natural way in which subsystems are cast into subproblems, resource- directive decomposition methods of mathematical programming problems have attracted considerable attention in recent years. A review of the specialized literature is presented in this paper, where the features and drawbacks of the most representative resource-directive methods are analyzed. To give an appropriate chronological and technical perspective, early general methods, such as the ones of Dantzig-Wolfe and Benders, are also included in the survey. [ABSTRACT FROM AUTHOR]
- Published
- 1979
- Full Text
- View/download PDF
9. On the Competitive Ratio of Evaluating Priced Functions.
- Author
-
CICALESE, FERDINANDO and LABER, EDUARDO SANY
- Subjects
ALGORITHMS ,MATHEMATICAL models ,MATHEMATICAL functions ,LINEAR programming ,MATHEMATICAL optimization ,MATHEMATICAL programming - Abstract
Let f be a function on a set of variables V. For each x ∈ V, let c(x) be the cost of reading the value of x. An algorithm for evaluating f is a strategy for adaptively identifying and reading a set of variables U ⊆ V whose values uniquely determine the value of f . We are interested in finding algorithms which minimize the cost incurred to evaluate f in the above sense. Competitive analysis is employed to measure the performance of the algorithms. We address two variants of the above problem. We consider the basic model in which the evaluation algorithm knows the cost c(x), for each x ∈ V. We also study a novel model where the costs of the variables are not known in advance and some preemption is allowed in the reading operations. This model has applications, for example, when reading a variable coincides with obtaining the output of a job on a CPU and the cost is the CPU time. For the model where the costs of the variables are known, we present a polynomial time algorithm with the best possible competitive ratio γ f c for each function f that is representable by a threshold tree and for each fixed cost function c(·). Remarkably, the best-known result for the same class of functions is a pseudo-polynomial algorithm with competitiveness 2γ f c . Still in the same model, we introduce the Linear Programming Approach (LPA), a framework that allows the design of efficient algorithms for evaluating functions. We show that different implementations of this approach lead in general to the best algorithms known so far—and in many cases to optimal algorithms—for different classes of functions considered before in the literature. Via the LPA, we are able to determine exactly the optimal extremal competitiveness of monotone Boolean functions. Remarkably, the upper bound which leads to this result, holds for a much broader class of functions, which also includes the whole set of Boolean functions. We also show how to extend the LPA (together with these results) to the model where the costs of the variables are not known beforehand. In particular, we show how to employ the extended LPA to design a polynomial-time optimal (with respect to competitiveness) algorithm for the class of monotone Boolean functions representable by threshold trees. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
10. On the Impossibility of Dimension Reduction in ℓ1.
- Author
-
Brinkman, Bo and Charikar, Moses
- Subjects
GENERALIZED spaces ,FUNCTION spaces ,LINEAR programming ,MATHEMATICAL programming ,ALGORITHMS - Abstract
The Johnson-Lindenstrauss lemma shows that any n points in Euclidean space (i.e., ℝ
n with distances measured under the ℓ2 norm) may be mapped down to O((log n)/ε²) dimensions such that no pairwise distance is distorted by more than a (1 + ε) factor. Determining whether such dimension reduction is possible in ℓ1 has been an intriguing open question. We show strong lower bounds for general dimension reduction in ℓ1 . We give an explicit family of n points in ℓ1 such that any embedding with constant distortion D requires nΩ(1/D²) dimensions. This proves that there is no analog of the Johnson-Lindenstrauss lemma for ℓ1 ; in fact, embedding with any constant distortion requires nΩ(1) dimensions. Further, embedding the points into ℓ1 with (1 + ε) distortion requires n½-O(ε(1/ε)) dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. We expect that the tools and techniques we develop will be useful for future investigations of embeddings into ℓ1 . [ABSTRACT FROM AUTHOR]- Published
- 2005
- Full Text
- View/download PDF
11. A Mathematical Programming Updating Method Using Modified Givens Transformations and Applied to LP Problems.
- Author
-
Hanson, Richard J., Wisniewski, John A., and Shanno, D. F.
- Subjects
MATHEMATICAL programming ,ALGORITHMS ,COMPUTER programming ,STATISTICAL correlation ,ESTIMATION theory ,MATHEMATICAL statistics - Abstract
An efficient and numerically stable method is presented for the problem of updating an orthogonal decomposition of a matrix of column (or row) vectors. The fundamental idea is to add a column (or row) analogous to adding an additional row of data in a linear least squares problem. A column (or row) is dropped by a formal scaling with the imaginary unit, √-1, followed by least squares addition of the column (or row). The elimination process for the procedure is successive application of the Givens transformation in modified (more efficient) form. These ideas are illustrated with an implementation of the revised simplex method. The algorithm is a general purpose one that does not account for any particular structure or sparsity in the equations. Some suggested computational tests for determining signs of various controlling parameters in the revised simplex algorithm are mentioned. A simple means of constructing test cases and some sample computing times are presented. [ABSTRACT FROM AUTHOR]
- Published
- 1979
- Full Text
- View/download PDF
12. Management Science: A View from Nonlinear Programming.
- Author
-
Shanno, David F. and Weil, Roman L.
- Subjects
NONLINEAR programming ,INTEGER programming ,MATHEMATICAL programming ,COMPUTER software development ,COMPUTER programming management ,DECISION theory ,MANAGEMENT science ,ALGORITHMS ,MATHEMATICAL models of decision making - Abstract
A brief history of integer and continuous nonlinear programming is presented as well as the current obstacles to practical use of these mathematical programming techniques It is forecast that the useful contributions to nonlinear programming actualls made in the next few years are more likely to he consolidations than theoretical breakthroughs These contributions are likely to be the documentation of standard test problems, construction of user oriented software, and comparisons of currently known algorithms to demonstrate which techniques are best for specific problems. [ABSTRACT FROM AUTHOR]
- Published
- 1972
- Full Text
- View/download PDF
13. Quadratic Programming for Nonlinear Regression.
- Author
-
Shrager, Richard I. and Timlake, W. P.
- Subjects
QUADRATIC programming ,ALGORITHMS ,REGRESSION analysis ,NONLINEAR programming ,MATHEMATICAL statistics ,MATHEMATICAL programming - Abstract
A quadratic programming algorithm is described for use with the magnified diagonal method of nonlinear regression with linear constraints. The regression method is published in JACM, July 1970. [ABSTRACT FROM AUTHOR]
- Published
- 1972
- Full Text
- View/download PDF
14. Reconstruction of Pictures from Their Projections.
- Author
-
Gordon, Richard, Herman, Gabor T., and Newman, W.
- Subjects
MEDICINE ,PHOTOGRAPHY ,PICTURES ,ALGORITHMS ,MICROGRAPHICS ,X-rays - Abstract
There are situations in the natural sciences and medicine (e.g. in electron microscopy and X-ray photography in which it is desirable to estimate the gray levels of a digital picture at the individual points from the sums of the gray levels along straight tines (projections) at a Few angles. Usually, in such situations, the picture is far from determined and the problem is to find the "most representative" picture. Three algorithms are described (all using Monte Carlo methods which were designed to solve this problem. The algorithms are applicable in a large and varied number of fields. The most important uses may he the reconstruction of possibly asymmetric particles from electron micrographs and three-dimensional X-ray analysis. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
15. A Note on Minimal Length Polygonal Approximation to a Digitized Contour.
- Author
-
Lawson, C. L. and Montanari, U.
- Subjects
POLYGONAL numbers ,DIGITAL images ,ALGORITHMS ,APPROXIMATION theory ,NONLINEAR programming ,MATHEMATICAL programming - Abstract
A method for extracting a smooth polygonal contour from a digitized image is illustrated. The ordered sequence of contour points and the connection graph of the image are first obtained by a modified Ledley algorithm in one image scan. A minimal perimeter polygon subjected to specified constraints is then chosen as the approximating contour. The determination of the minimal polygon can be reduced to a nonlinear programming problem, solved by an algorithm which takes into account the weak bonds between variables. Some examples are presented, and the corresponding computing times are listed. [ABSTRACT FROM AUTHOR]
- Published
- 1970
16. Letters to the Editor.
- Author
-
Bell, E. J., Jennings, C., Huber, Hartmut G. M., Knuth, Donald E., Rosin, Robert F., and Lions, John
- Subjects
LETTERS to the editor ,LINEAR programming ,ALGORITHMS ,MATHEMATICAL programming ,COMPUTER programming ,COMPUTER algorithms ,FUNCTIONAL equations ,PROGRAMMING languages - Abstract
Several letters to the editor are presented in response to articles in the previous issues including "A Comparison of the Primal-Simplex and Primal-Dual Algorithms for Linear Programming," by R.K. Mueller and L. Cooper, "Algorithm and Formula," by T. Wangsness and J. Franklin, and a letter which further expounded the terms algorithm and program.
- Published
- 1966
17. Algorithms.
- Author
-
Herriot, J. G.
- Subjects
ALGORITHMS ,PROGRAMMING languages ,ALGOL (Computer program language) ,COMPUTER algorithms ,ALGEBRA ,MATHEMATICAL programming ,EQUATIONS ,COMPUTER programming ,MATHEMATICS ,FORTRAN - Abstract
The article reports on several algorithms with their specific computational dynamics. A specific algorithm with its corresponding formula which provides for the procedure for deriving a certain value is provided. The algorithms include, among others, algorithm 290 for linear equations, algorithm 291 for logarithm of gamma functions, and algorithm 178 for direct search. Moreover, the algorithms are written in the ALGOL 60 Reference Language, Standard FORTRAN, and Basic FORTRAN. Specific instructions on how to submit algorithms are also included.
- Published
- 1966
18. Solution of Systems of Polynomial Equations By Elimination.
- Author
-
Moses, Joel
- Subjects
ELIMINATION (Mathematics) ,EQUATIONS ,POLYNOMIALS ,COMPUTER programming ,MATHEMATICAL programming ,ALGORITHMS - Abstract
The elimination procedure as described by Williams has been coded in LISP and FORMAC and used in solving systems of polynomial equations. It is found that the method is very effective in the case of small systems, where it yields all solutions without the need for initial estimates. The method, by itself, appears inappropriate, however, in the solution of large systems of equations due to the explosive growth in the intermediate equations and the hazards which arise when the coefficients are truncated. A comparison is made with difficulties found in other problems in non-numerical mathematics such as symbolic integration and simplification. [ABSTRACT FROM AUTHOR]
- Published
- 1966
- Full Text
- View/download PDF
19. Symbolic Factoring of Polynomials in Several Variables.
- Author
-
Jordan, Dale E., Kain, Richard Y., and Clapp, Lewis C.
- Subjects
POLYNOMIALS ,ALGORITHMS ,FACTORS (Algebra) ,MATHEMATICAL programming ,NUMERICAL analysis ,MATHEMATICAL analysis - Abstract
An algorithm for finding the symbolic factors of multivariate polynomial with integer coefficients is presented. The algorithm is an extension of a technique used by Kronecker in a proof that the prime factoring of any polynomial may be found in a finite number of steps. The algorithm consists of factoring single-variable instances of the given polynomial by Kronecker's method and introducing the remaining variables by interpolation. Techniques for implementing the algorithm and several examples are discussed. The algorithm promises sufficient power to be used efficiently in an online system for symbolic mathematics. [ABSTRACT FROM AUTHOR]
- Published
- 1966
- Full Text
- View/download PDF
20. Deterministic Distributed Vertex Coloring in Polylogarithmic Time.
- Subjects
DISTRIBUTED computing ,GRAPH theory ,COMPUTER architecture ,ALGORITHMS ,COMPUTATIONAL mathematics ,MATHEMATICAL programming - Abstract
Consider an n-vertex graph G = (V, E) of maximum degree ?, and suppose that each vertex v ? V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, that is, it proceeds in discrete rounds. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.