Revealed preference theory: An algorithmic outlook

Revealed preference theory is a domain within economics that studies rationalizability of behavior by (certain types of) utility functions. Given observed behavior in the form of choice data, testing whether certain conditions are satisfied gives rise to a variety of computational problems that can be analyzed using operations research techniques. In this survey, we provide an overview of these problems, their theoretical complexity, and available algorithms for tackling them. We focus on consumer choice settings, in particular individual choice, collective choice and stochastic choice settings.     

An algorithmic Littlewood-Richardson rule

We introduce a Littlewood-Richardson rule based on an algorithmic deformation of skew Young diagrams and present a bijection with the classical rule. The result is a direct combinatorial interpretation and proof of the geometric rule presented by Coskun (2000). We also present a corollary regarding the Specht modules of the intermediate diagrams.     

An Iterative FEM for Solving Wave Problems of a Halfspace

An iterative finite element method for solving wave problems of a halfspace is presented in this paper. The halfspace is first truncated by introducing a fictive finite boundary on which some fictive boundary conditions must be imposed. A finite computational domain is in each iteration subjected to actual boundary conditions on real boundary and to fictive Dirichlet or Neumann boundary conditions on the fictive boundary. The radiation condition is satisfied by using DtN operator. The DtN operator is not introduce in the finite element formulation on the fictive boundary so any finite elements can be used. The method is simple and specially useful for computing higher harmonics.     

Self-similar fractals: An algorithmic point of view

This paper studies the self-similar fractals with overlaps from an algorithmic point of view.A decidable problem is a question such that there is an algorithm to answer"yes"or"no"to the question for every possible input.For a classical class of self-similar sets{E b.d}b,d where E b.d=Sn i=1(E b,d/d+b i)with b=(b1,...,b n)∈Qn and d∈N∩[n,∞),we prove that the following problems on the class are decidable:To test if the Hausdorff dimension of a given self-similar set is equal to its similarity dimension,and to test if a given self-similar set satisfies the open set condition(or the strong separation condition).In fact,based on graph algorithm,there are polynomial time algorithms for the above decidable problem.     

An algorithmic hypergraph regularity lemma

Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.     

An algorithmic approach to Hermite-Birkhoff-interpolation

Summary This paper deals with an algorithmic approach to the Hermite-Birkhoff-(HB)interpolation problem. More precisely, we will show that Newton's classical formula for interpolation by algebraic polynomials naturally extends to HB-interpolation. Hence almost all reasons which make Newton's method superior to just solving the system of linear equations associated with the interpolation problem may be repeated. Let us emphasize just two: Newton's formula being a biorthogonal expansion has a well known permanence property when the system of interpolation conditions grows. From Newton's formula by an elementary argument due to Cauchy an important representation of the interpolation error can be derived. All of the above extends to HB-interpolation with respect to canonical complete ebyev-systems and naturally associated differential operators [7]. A numerical example is given.     

Path assignment for call routing: An application of tabu search

We describe an implementation of tabu search that solves the path assignment problem, which is the problem of routing video data through an undercapacitated telecommunications network. Two versions of the tabu search were studied. Our results compare very favourably with those from other methods.This research was supported by a grant from the Colorado Advanced Software Institute. The work of Jennifer Ryan was also partially supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract #F49620-90-C-0033.     

Focused simulated annealing search: An application to job shop scheduling

This paper presents a simulated annealing search procedure developed to solve job shop scheduling problems simultaneously subject to tardiness and inventory costs. The procedure is shown to significantly increase schedule quality compared to multiple combinations of dispatch rules and release policies, though at the expense of intense computational efforts. A meta-heuristic procedure is developed that aims at increasing the efficiency of simulated annealing by dynamically inflating the costs associated with major inefficiencies in the current solution. Three different variations of this procedure are considered. One of these variations is shown to yield significant reductions in computation time, especially on problems where search is more likely to get trapped in local minima. We analyze why this variation of the meta-heuristic is more effective than the others.     

An algorithmic characterization of total digraphs

We consider total digraphs of digraphs and present: (i) a structural characterization, (ii) an algorithmic characterization based on a labeling procedure, and (iii) an efficient recognition algorithm. The computational complexity of the algorithm is dominated by the complexity of finding the square of a Boolean (adjacency) matrix of a digraph.     

Nonsingular systems of generalized Sylvester equations: An algorithmic approach

We consider the uniqueness of solution (i.e., nonsingularity) of systems of r generalized Sylvester and ?‐Sylvester equations with n×n coefficients. After several reductions, we show that it is sufficient to analyze periodic systems having, at most, one generalized ?‐Sylvester equation. We provide characterizations for the nonsingularity in terms of spectral properties of either matrix pencils or formal matrix products, both constructed from the coefficients of the system. The proposed approach uses the periodic Schur decomposition and leads to a backward stable O(n³r) algorithm for computing the (unique) solution.     

Finding intersection of rectangles by range search

Three related rectangle intersection problems in k-dimensional space are considered: (1) find the intersections of a rectangle with a given set of rectangles, (2) find the intersecting pairs of rectangles as they are inserted into or deleted from an existing set of rectangles, and (3) find the intersecting pairs of a given set of rectangles. By transforming these problems into range search problems, one need not divide the intersection problem into two subproblems, namely, the edge-intersecting problem and the containment problem, as done by many previous studies. Furthermore, this approach can also solve these subproblems separately, if required. For the first problem the running time is O((log n)^2k−1 + s), where s is the number of intersecting pairs of rectangles. For the second problem the time needed to generate and maintain n rectangles is O(n(log n)^2k) and the time for each query is O((log n)^2k−1 + s). For the third problem the total time is O(n log n + n(log n)^2(k−1) + s) for k ≥ 1.     

An algorithmic criterion for basicness in dimension 2

In this paper we give a geometric constructive procedure to check basicness of open (or closed) semialgebraic sets in surfaces; we get also a criterion for principality. These criterions allow us to give a geometric proof of the Bröcker’s 4-elements fans criterion for surfaces.     

An algorithmic sign-reversing involution for special rim-hook tableaux

Eğecioğlu and Remmel [Linear Multilinear Algebra 26 (1990) 59–84] gave an interpretation for the entries of the inverse Kostka matrix K⁻¹ in terms of special rim-hook tableaux. They were able to use this interpretation to give a combinatorial proof that KK⁻¹=I but were unable to do the same for the equation K⁻¹K=I. We define an algorithmic sign-reversing involution on rooted special rim-hook tableaux which can be used to prove that the last column of this second product is correct. In addition, following a suggestion of Chow [preprint, math.CO/9712230, 1997] we combine our involution with a result of Gasharov [Discrete Math. 157 (1996) 193–197] to give a combinatorial proof of a special case of the (3+1)-free Conjecture of Stanley and Stembridge [J. Combin. Theory Ser. A 62 (1993) 261–279].     

Cyclic irreducible non-holonomic modules over the Weyl algebra: An algorithmic characterization

Let K be a field of characteristic zero, n≥1 an integer and A_n+1=K[X,Y₁,…,Y_n]〈∂_X,∂_Y1,…,∂_Yn〉 the (n+1)th Weyl algebra over K. Let S∈A_n+1 be an order-1 differential operator of the type with a_i,b_i∈K[X] and g_i∈K[X,Y_i] for every i=1,…,n. We construct an algorithm that allows one to recognize whether S generates a maximal left ideal of A_n+1, hence also whether A_n+1/A_n+1S is an irreducible non-holonomic A_n+1-module. The algorithm, which is a powerful instrument for producing concrete examples of cyclic maximal left ideals of A_n, is easy to implement and quite useful; we use it to solve several open questions.The algorithm also allows one to recognize whether certain families of algebraic differential equations have a solution in K[X,Y₁,…,Y_n] and, when they have one, to compute it.