Guarantees for the success frequency of an algorithm for finding Dodgson-election winners

In the year 1876 the mathematician Charles Dodgson, who wrote fiction under the now more famous name of Lewis Carroll, devised a beautiful voting system that has long fascinated political scientists. However, determining the winner of a Dodgson election is known to be complete for the Θ ₂ ^p level of the polynomial hierarchy. This implies that unless P=NP no polynomial-time solution to this problem exists, and unless the polynomial hierarchy collapses to NP the problem is not even in NP. Nonetheless, we prove that when the number of voters is much greater than the number of candidates—although the number of voters may still be polynomial in the number of candidates—a simple greedy algorithm very frequently finds the Dodgson winners in such a way that it “knows” that it has found them, and furthermore the algorithm never incorrectly declares a nonwinner to be a winner.     

On finding an envy-free Pareto-optimal division

This paper describes an algorithm to find an (α-)envy-free Pareto-optimal division in the case of a finite number of homogeneous infinitely divisible goods and linear utility functions. It is used to find an allocation in the classical cake division problem that is almost Pareto-optimal and α-envy-free.     

A polynomial-time algorithm for finding zero-sums

Erdös, Ginzburg and Ziv proved that any sequence of 2n−1 (not necessary distinct) members of the cyclic group Z_n contains a subsequence of length n the sum of whose elements is congruent to zero modulo n. There are several proofs of this celebrated theorem which combine combinatorial and algebraic ideas. Our main result is an alternative and constructive proof of this result. From this proof, we deduce a polynomial-time algorithm for finding a zero-sum n-sequence of the given (2n−1)-sequence of an abelian group G with n elements (a fortiori for Z_n). To the best of our knowledge, this is the first efficient algorithm for finding zero-sum n-sequences.     

An improved computational algorithm for finding the factorial

In the present paper, we consider a method for improving the computational algorithm for finding the factorials of integers; this method linearly accelerates the computations. We also present several algorithms effectively realizing this method and analyze their complexity.     

Analysis of PSLQ, an integer relation finding algorithm

Let be either the real, complex, or quaternion number system and let be the corresponding integers. Let be a vector in . The vector has an integer relation if there exists a vector , , such that . In this paper we define the parameterized integer relation construction algorithm PSLQ, where the parameter can be freely chosen in a certain interval. Beginning with an arbitrary vector , iterations of PSLQ will produce lower bounds on the norm of any possible relation for . Thus PSLQ can be used to prove that there are no relations for of norm less than a given size. Let be the smallest norm of any relation for . For the real and complex case and each fixed parameter in a certain interval, we prove that PSLQ constructs a relation in less than iterations.

     

A pseudo-polynomial algorithm for optimal capacitor placement on electric power distribution networks

Allocation of shunt capacitor banks on radial electric power distribution networks allow reduction of energy losses and aggregated benefits. Four decades ago Durán proposed the use of dynamic programming to find optimal capacitor placement on these networks; however, with the restricting assumption of single-ended networks, which precluded its application to real capacitor allocation problems. Subsequently heuristic methods prevailed in the capacitor allocation literature. Here the Extended Dynamic Programming Approach (EDP) lifts Durán’s restricting assumption; a richer definition of state and the projection of multidimensional informations into equivalent one-dimensional representations are the supporting concepts. In addition to allow consideration of multi-ended networks, EDP deals with other requirements of capacitor allocation studies, including the use of both fixed and switched capacitors and representation of voltage drops along the networks. When switched capacitors are considered the optimization procedure also solves the capacitor control problem, obtaining the best tap adjustments for them. Case studies with real scale distribution networks put into perspective the benefits of the methodology; EDP has the appeal of providing global optimal solutions with pseudo-polynomial computational complexity in the worst-case, and with linear complexity for practical applications.     

Computational results on an algorithm for finding all vertices of a polytope

This paper provides answers to several questions raised by V. Klee regarding the efficacy of Mattheiss' algorithm for finding all vertices of convex polytopes. Several results relating to the expected properties of polytopes are given which indicate thatn-polytopes defined by large numbers of constraints are difficult to obtain by random processes, the expected value of the number of vertices of polytope is considerably less than Klee's least upper bound the expected performance of Mattheiss' algorithm is far better than Klee's upper bound would suggest.     

An algorithm for finding planar surfaces in three-manifolds

By a slope in the boundary ∂M of a 3-manifold, we mean the isotopy class α of a finite set of disjoint simple closed curves in ∂M that are nontrivial and pairwise nonparallel. In this paper, we construct an algorithm to decide whether or not a given orientable 3-manifold M contains an essential planar surface whose boundary has a given slope α. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 4, pp. 197–202, 2005.     

On finding the nucleolus of an n-person cooperative game

Kohlberg (1972) has shown how the nucleolus for ann-person game with side-payments may be found by solving a single minimization LP in case the imputation space is a polytope. However the coefficients in the LP have a very wide range even for problems with 3 or 4 players. Therefore the method is computationally viable only for small problems on machines with finite precision. Maschler et al. (1979) find the nucleolus by solving a sequence of minimization LPs with constraint coefficients of either –1, 0 or 1. However the number of LPs to be solved is o(4 ⁿ ). In this paper, we show how to find the nucleolus by solving a sequence of o(2 ⁿ ) LPs whose constraint coefficients are –1, 0 or 1.     

The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank

The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent, consensus, networked control and data mining. The power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones; they require much less calculations for one iteration and are well tailored for distributed computations. We propose a new randomized algorithm and provide upper bound for its rate of convergence which is O(lnN/n), where N is the dimension and n is the number of iterations. The bound looks promising because lnN is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization. Applications to PageRank problem are discussed. Published in Russian in Doklady Akademii Nauk, 2009, Vol. 426, No. 6, pp. 734–737. Presented by Academician S.N. Vasil’ev February 9, 2009 The article was translated by the authors.     

An algorithm for finding the nucleolus of assignment games

Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market. An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite number of payoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated into determining the lengths of longest paths to the nodes, if the graph is acyclic, or otherwise, detecting the cycle(s). In an (m,n)-person assignment game withm = min(m,n) the nucleolus is found in at most 1/2·m(m + 3) steps, each one requiring at mostO(m·n) elementary operations.     

A linear-time algorithm for finding an edge-partition with max-min ratio at most two

Given a positive integer $k$ and an undirected edge-weighted connected simple graph $G$ with at least $k$ edges of positive weight, we wish to partition the graph into $k$ edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the max-min ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible.     

A potential reduction algorithm for an extended SDP problem

An extended semi-definite programming, the SDP with an additional quadratic term in the objective function, is studied. Our generalization is similar to the generalization from linear programming to quadratic programming. Optimal conditions for this new class of problems are discussed and a potential reduction algorithm for solving QSDP problems is presented. The convergence properties of this algorithm are also given.     

Scattering on an anisotropic potential in a constant electric field

The scattering of a particle on an anisotropic potential in a constant electric field is considered. Conditions on the anisotropic decay of the potential that insure asymptotic completeness without modifications of the wave operators are obtained. The paper uses the mixed approach wherein the Enss method is applied to one part of the variables, whereas the other part is treated using the smoothness technique. Bibliography: 12 titles. Translated fromZapiski Naucnykh Seminarov POMI, Vol. 230, 1995, pp. 203–214. Translated by A. B. Pushnitskii.     

Semicrystal with a singular potential in an accelerating electric field

We study the Schrödinger equation describing the one-dimensional motion of a quantum electron in a periodic crystal placed in an accelerating electric field. We describe the asymptotic behavior of equation solutions at large values of the argument. Analyzing the obtained asymptotic expressions, we present rather loose conditions on the potential under which the spectrum of the corresponding operator is purely absolutely continuous and spans the entire real axis.     

Probabilistic algorithm for finding roots of linearized polynomials

A probabilistic algorithm is presented for finding a basis of the root space of a linearized polynomial

A contraction algorithm for finding small cycle cutsets

We consider the problem of finding a minimum size cutset in a directed graph G = (V, E), i.e., a vertex set that cuts all cycles in G. Since the general problem is NP-complete we concentrate on finding small cutsets. The algorithm we suggest uses contraction operations to reduce the graph size and to identify candidates for the cutset; the complexity of the algorithm is O(|E|log|V|). This contraction algorithm is compared to Shamir-Rosen algorithm. It is shown that the class of graphs for which the contraction algorithm finds a minimum cutset (completely contractible graphs) properly contains the class of graphs for which Shamir-Rosen algorithm finds a minimum cutset (quasi-reducible graphs) and thus that the contraction algorithm is more powerful. As a by-product of this analysis we construct a hierarchy of the classes of graphs for which minimum cutsets can be found efficiently. The class of quasi-reducible graphs lies, in this hierarchy, between two classes which are closely related. This result illuminates the nature of the quasi-reducible graphs. The hierarchy constructed allows us also to compare the Wang-Lloyd-Soffa algorithm to the Shamir-Rosen algorithm and to the contraction algorithm.