Abstract We consider the fundamental problem of fairly allocating a set of indivisible items among agents having valuations that are represented by a multi-graph – here, agents appear as vertices and items as edges between them and each vertex (agent) only values the set of its incident edges (items). The goal is to find a fair, i.e., envy-free up to any item ( $$\textsf {EFX}$$ ) allocation. This model has recently been introduced by [22] where they show that $$\textsf {EFX}$$ allocations always exist on simple graphs for monotone valuations, i.e., where any two agents can share at most one edge (item). A natural question arises as to what happens when we go beyond simple graphs and study various classes of multi-graphs? We answer the above question affirmatively for the valuation class of bipartite multi-graphs and multi-cycles . The main contribution of this work is to establish the existence of $$\textsf {EFX}$$ allocations on bipartite multi-graphs for monotone valuations and on multi-cycles for $$\textsf {MMS}$$ -feasible valuations. We also present pseudo-polynomial time algorithms to compute $$\textsf {EFX}$$ allocations for the above settings. Furthermore, we show that for bipartite multi-graphs with cancelable valuations, $$\textsf {EFX}$$ allocations can be computed in polynomial time. We thus deepen the understanding of $$\textsf {EFX}$$ allocations by expanding the spectrum of settings in which they are guaranteed to exist for an arbitrary number of agents. Next, we study $$\textsf {EFX}$$ orientations (allocations where every item is assigned to one of its two endpoint agents) and provide a complete characterization of their existence on bipartite multi-graphs in terms of two key parameters—the number of edges shared between any two agents and the diameter of the graph. Finally, we prove that it is $$\textsf {NP}$$ -complete to determine whether a given fair division instance on a bipartite multi-graph admits an $$\textsf {EFX}$$ orientation, even with a constant number of agents.

Abstract We present the first formal correctness proof of Edmonds’ blossom shrinking algorithm for maximum cardinality matching in general graphs. We focus on formalising the mathematical structures and properties that allow the algorithm to run in worst-case polynomial running time. We formalise Berge’s lemma, blossoms and their properties, and a mathematical model of the algorithm, showing that it is totally correct. We provide the first detailed proofs of many of the facts underlying the algorithm’s correctness.

Serial dictatorship is a simple mechanism for coordinating agents in solving combinatorial optimization problems according to their preferences. The most representative such problem is one-sided matching, in which a set of n agents have values for a set of n items, and the objective is to compute a matching of the agents to the items of maximum total value (a.k.a., social welfare). Following the recent framework of Caragiannis and Rathi (2023), we consider a model in which the agent-item values are not available upfront but become known by querying agent sequences. In particular, when the agents are asked to act in a sequence, they respond by picking their favorite item that has not been picked by agents who acted before and reveal their value for it. Can we compute an agent sequence that induces a social welfare-optimal matching? We answer this question affirmatively and present an algorithm that uses polynomial number (specifically, O(n^5) of queries). This solves the main open problem stated by Caragiannis and Rathi (2023). Our analysis uses a potential function argument that measures progress towards learning the underlying edge-weight information. Furthermore, the algorithm has a truthful implementation by adapting the paradigm of VCG payments.

We study the problem of distributing a set of indivisible goods among agents with additive valuations in a fair manner. The fairness notion under consideration is envy-freeness up to any good (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this article, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture of Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some goods are not allocated) with higher Nash welfare than that of any complete EFX allocation.

We study fair division of indivisible chores among n agents with additive disutility functions. Two well-studied fairness notions for indivisible items are envy-freeness up to one/any item (EF1/EFX) and the standard notion of economic efficiency is Pareto optimality (PO). There is a noticeable gap between the results known for both EF1 and EFX in the goods and chores settings. The case of chores turns out to be much more challenging. We reduce this gap by providing slightly relaxed versions of the known results on goods for the chores setting. Interestingly, our algorithms run in polynomial time, unlike their analogous versions in the goods setting. We introduce the concept of k surplus in the chores setting which means that up to k more chores are allocated to the agents and each of them is a copy of an original chore. We present a polynomial-time algorithm which gives EF1 and PO allocations with n-1 surplus. We relax the notion of EFX slightly and define tEFX which requires that the envy from agent i to agent j is removed upon the transfer of any chore from the i's bundle to j's bundle. We give a polynomial-time algorithm that in the chores case for 3 agents returns an allocation which is either proportional or tEFX. Note that proportionality is a very strong criterion in the case of indivisible items, and hence both notions we guarantee are desirable.

We consider the problem of guaranteeing maximin-share ($\MMS$) when allocating a set of indivisible items to a set of agents with fractionally subadditive ($\XOS$) valuations. For $\XOS$ valuations, it has been previously shown that for some instances no allocation can guarantee a fraction better than $1/2$ of maximin-share to all the agents. Also, a deterministic allocation exists that guarantees $0.219225$ of the maximin-share of each agent. Our results involve both deterministic and randomized allocations. On the deterministic side, we improve the best approximation guarantee for fractionally subadditive valuations to $3/13 = 0.230769$. We develop new ideas on allocating large items in our allocation algorithm which might be of independent interest. Furthermore, we investigate randomized algorithms and the Best-of-both-worlds fairness guarantees. We propose a randomized allocation that is $1/4$-$\MMS$ ex-ante and $1/8$-$\MMS$ ex-post for $\XOS$ valuations. Moreover, we prove an upper bound of $3/4$ on the ex-ante guarantee for this class of valuations.

The existence of EFX allocations is a fundamental open problem in discrete fair division. Since the general problem has been elusive, progress is made on two fronts: (i) proving existence when the number of agents is small, and (ii) proving the existence of relaxations of EFX. In this paper, we improve and simplify the state-of-the-art results on both fronts with new techniques.

We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent for every good is either p or q, where p and q are integers and p2. In terms of approximation, we present positive and negative results for general p and q. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is APX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.

We study the fair and efficient allocation of a set of indivisible goods among agents, where each good has several copies, and each agent has an additively separable concave valuation function with a threshold. These valuations capture the property of diminishing marginal returns, and they are more general than the well-studied case of additive valuations. We present a polynomial-time algorithm that approximates the optimal Nash social welfare (NSW) up to a factor of e1/e ≈ 1.445. This matches with the state-of-the-art approximation factor for additive valuations. The computed allocation also satisfies the popular fairness guarantee of envy-freeness up to one good (EF1) up to a factor of 2 + ε. For instances without thresholds, it is also approximately Pareto-optimal. For instances satisfying a large market property, we show an improved approximation factor. Lastly, we show that the upper bounds on the optimal NSW introduced in Cole and Gkatzelis (2018) and Barman et al. (2018) have the same value.

We study the problem of fairly allocating a set of indivisible goods among n agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division [5]. Towards resolving this problem, many impressive results show the existence of its relaxations. In particular, [1] shows the existence of 0.618-EFX allocations, and [4] shows that EFX allocation exists if we do not allocate at most n - 1 goods. The latter result was recently improved for three agents in [2], in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for an arbitrary number of agents is a systematic way to settle the big question.

We study the problem of distributing a set of indivisible items among agents with additive valuations in a fairmanner. The fairness notion under consideration is Envy-freeness up to anyitem (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al.[9] by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.

Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute m goods to n agents in a “fair” manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is “envy-freeness up to any good” (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when n = 3. We show there is always a partition of the set of goods into n + 1 subsets (X1, …, Xn, P) where for i ϵ [n], Xi is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that we have: (1) envy-freeness up to any good, (2) no agent values P higher than her own bundle, and (3) fewer than n goods go to charity, i.e., |P| < n (typically m ≫ n). Our proof is constructive. When agents have additive valuations and |P| is large (i.e., when |P| is close to n), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is 4/7 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 1/2 known for an approximate GMMS allocation.

The goal of the LEDA project was to build an easy-to-use and extendable library of correct and efficient data structures, graph algorithms and geometric algorithms. We report on the use of formal program verification to achieve an even higher level of trustworthiness. Specifically, we report on an ongoing and largely finished verification of the blossom-shrinking algorithm for maximum cardinality matching.

We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric mean of the utilities of the agents. Each good comes in multiple items or copies, and the utility of an agent diminishes as it receives more items of the same good. The utility of a bundle of items for an agent is the sum of the utilities of the items in the bundle. Each agent has a utility cap beyond which he does not value additional items. We give a polynomial time approximation algorithm that maximizes Nash social welfare up to a factor of e^{1/{e}} ~~ 1.445. The computed allocation is Pareto-optimal and approximates envy-freeness up to one item up to a factor of 2 + epsilon.

We present a combinatorial algorithm for determining the market clearing prices of a general linear Arrow-Debreu market, where every agent can own multiple goods. The existing combinatorial algorithms for linear Arrow-Debreu markets consider the case where each agent can own all of one good only. We present an $\tilde{\mathcal{O}}((n+m)^7 \log^3(UW))$ algorithm where $n$, $m$, $U$ and $W$ refer to the number of agents, the number of goods, the maximal integral utility and the maximum quantity of any good in the market respectively. The algorithm refines the iterative algorithm of Duan, Garg and Mehlhorn using several new ideas. We also identify the hard instances for existing combinatorial algorithms for linear Arrow-Debreu markets. In particular we find instances where the ratio of the maximum to the minimum equilibrium price of a good is $U^{Ω(n)}$ and the number of iterations required by the existing iterative combinatorial algorithms of Duan, and Mehlhorn and Duan, Garg, and Mehlhorn are high. Our instances also separate the two algorithms.

Does there exist O(1)-competitive (self-adjusting) binary search tree (BST) algorithms? This is a well-studied problem. A simple offline BST algorithm GreedyFuture was proposed independently by Lucas and Munro, and they conjectured it to be O(1)-competitive. Recently, Demaine et al. gave a geometric view of the BST problem. This view allowed them to give an online algorithm GreedyArb with the same cost as GreedyFuture. However, no o(n)-competitive ratio was known for GreedyArb. In this paper we make progress towards proving O(1)-competitive ratio for GreedyArb by showing that it is O(\log n)-competitive.

We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every ε > 0, our algorithm obtains a (2.404 + ε)-approximation in time polynomial in the input size and 1/ε. Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [17]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.

We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement this positive result with a number of hardness results for related computational questions. We prove that it isNP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good.

Spectral clustering is a popular and successful approach for partitioning the nodes of a graph into clusters for which the ratio of outside connections compared to the volume (sum of degrees) is small. In order to partition into k clusters, one first computes an approximation of the bottom k eigenvectors of the (normalized) Laplacian of G, uses it to embed the vertices of G into k-dimensional Euclidean space R^k, and then partitions the resulting points via a k-means clustering algorithm. It is an important task for theory to explain the success of spectral clustering. Peng et al. (COLT, 2015) made an important step in this direction. They showed that spectral clustering provably works if the gap between the (k+1)-th and the k-th eigenvalue of the normalized Laplacian is sufficiently large. They proved a structural and an algorithmic result. The algorithmic result needs a considerably stronger gap assumption and does not analyze the standard spectral clustering paradigm; it replaces spectral embedding by heat kernel embedding and k-means clustering by locality sensitive hashing. We extend their work in two directions. Structurally, we improve the quality guarantee for spectral clustering by a factor of k and simultaneously weaken the gap assumption. Algorithmically, we show that the standard paradigm for spectral clustering works. Moreover, it even works with the same gap assumption as required for the structural result.

We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with n agents and integral utilities bounded by U, the algorithm runs in O(n7 log3(nU)) time. This improves upon the previously best algorithm of Ye by a factor of . The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of . The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy.

R. Lavi and C. Swamy (FOCS 2005 , J. ACM 58 (6), 25, 2011 ) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.

The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e. One that is constant factor competitive with any BST on any input access sequence. The two main candidates for dynamic optimality in the literature are splay trees [Sleator and Tarjan, 1985], and Greedy [Lucas, 1988, Munro, 2000, Demaine et al. 2009]. Despite BSTs being among the simplest data structures in computer science, and despite extensive effort over the past three decades, the conjecture remains elusive. Dynamic optimality is trivial for almost all sequences: the optimum access cost of most length-n sequences is Theta(n log n), achievable by any balanced BST. Thus, the obvious missing step towards the conjecture is an understanding of the "easy" access sequences, and indeed the most fruitful research direction so far has been the study of specific sequences, whose "easiness" is captured by a parameter of interest. For instance, splay provably achieves the bound of O(nd) when d roughly measures the distances between consecutive accesses (dynamic finger), the average entropy (static optimality), or the delays between multiple accesses of an element(working set). The difficulty of proving dynamic optimality is witnessed by other highly restricted special cases that remain unresolved, one prominent example is the traversal conjecture [Sleator and Tarjan, 1985], which states that preorder sequences (whose optimum is linear) are linear-time accessed by splay trees, no online BST is known to satisfy this conjecture. In this paper, we prove two different relaxations of the traversal conjecture for Greedy: (i) Greedy is almost linear for preorder traversal, (ii) if a linear-time preprocessing is allowed, Greedy is in fact linear. These statements are corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. Pattern avoidance is a well-established concept in combinatorics, and the classes of input sequences thus defined are rich, e.g. The k = 3 case includes preorder sequences. For any sequence X with parameter k, our most general result shows that Greedy achieves the cost n*2(Α(n))O(k) where Α is the inverse Ackermann function. Furthermore, a broad subclass of parameter-k sequences has a natural combinatorial interpretation as k-decomposable sequences. For this class of inputs, we obtain an n*2O(k) bound for Greedy when preprocessing is allowed. For k = 3, these results imply (i) and (ii). To our knowledge, these are the first upper bounds for Greedy that are not known to hold for any other online BST. To obtain these results we identify an input-revealing property of Greedy. Informally, this means that the execution log partially reveals the structure of the access sequence. This property facilitates the use of rich technical tools from forbidden sub matrix theory. Further studying the intrinsic complexity of k-decomposable sequences, we make several observations. First, in order to obtain an offline optimal BST, it is enough to bound Greedy on non-decomposable access sequences. Furthermore, we show that the optimal cost for k-decomposable sequences is Theta(n log k), which is well below the proven performance of all known BST algorithms. Hence, sequences in this class can be seen as a "candidate counterexample" to dynamic optimality.

Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. In this paper, we address the computational cost of address translation in virtual memory. Starting point for our work is the observation that the analysis of some simple algorithms (random scan of an array, binary search, heapsort) in either the RAM model or the EM model (external memory model) does not correctly predict growth rates of actual running times. We propose the VAT model (virtual address translation) to account for the cost of address translations and analyze the algorithms mentioned above and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms.

Let G = (A union B, E) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r be the worst rank used. A matching M is fair in G if it has maximum cardinality, subject to this, M matches the minimum number of vertices to rank r neighbors, subject to that, M matches the minimum number of vertices to rank (r-1) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation---this can be of independent interest.

We present an algorithm for isolating all roots of an arbitrary complex polynomial p which also works in the presence of multiple roots provided that arbitrary good approximations of the coefficients of p and the number of distinct roots are given. Its output consists of pairwise disjoint disks each containing one of the distinct roots of p, and its multiplicity. The algorithm uses approximate factorization as a subroutine. For the case, where Pan's algorithm [16] is used for the factorization, we derive complexity bounds for the problems of isolating and refining all roots which are stated in terms of the geometric locations of the roots only. Specializing the latter bounds to a polynomial of degree d and with integer coefficients of bitsize less than τ, we show that Õ(d3+d2τ+dκ) bit operations are sufficient to compute isolating disks of size less than 2-κ for all roots of p, where κ is an arbitrary positive integer.

Physarum is a slime mold. It was observed over the past 10 years that the mold is able to solve shortest path problems and to construct good Steiner networks [9, 11, 8].In a nutshell, the shortest path experiment is as follows: A maze is covered with mold and food is then provided at two positions s and t and the evolution of the slime is observed. Over time, the slime retracts to the shortest s-t-path. A video showing the wet-lab experiment can be found at http://www.youtube.com/watch?v=tLO2n3YMcXw&t=4m43s. We strongly recommend to watch this video. A mathematical model of the slime's dynamic behavior was proposed in 2007 [10]. Extensive computer simulations of the mathematical model confirm the wet-lab findings. For the edges on the shortest path, the diameter converges to one, and for the edges off the shortest path, the diameter converges to zero. We review the wet-lab and the computer experiments and provide a proof for these experimental findings. The proof was developed over a sequence of papers [6, 7, 4, 2, 1, 3]. We recommend the last two papers for first reading. An interesting connection between Physarum and ant computations is made in [5].

Physarum Polycephalum is a slime mold that apparently is able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0-s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a “natural algorithm”, that is, an algorithm developed by evolution over millions of years.

Refereed conferences require every submission to be reviewed by members of a program committee (PC) in charge of selecting the conference program. There are many software packages available to manage the review process. Typically, in a bidding phase PC members express their personal preferences by ranking the submissions. This information is used by the system to compute an assignment of the papers to referees (PC members). We study the problem of assigning papers to referees . We propose to optimize a number of criteria that aim at achieving fairness among referees/papers. Some of these variants can be solved optimally in polynomial time, while others are NP-hard, in which case we design approximation algorithms. Experimental results strongly suggest that the assignments computed by our algorithms are considerably better than those computed by popular conference management software.

An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2 k −1, 0)-spanner of size O ( n 1+1/ k ) and an (additive) (1,2)-spanner of size O ( n 3/2 ). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (α, β)-spanners. Our first result is an additive (1,6)-spanner of size O ( n 4/3 ). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (α, β)-spanners can be computed efficiently, ideally in linear time. We show that, for any k , a ( k , k −1)-spanner with size O ( kn 1+1/ k ) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

We describe a bisection algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is deterministic and has almost the same asymptotic complexity as the randomized algorithm of [12]. We also discuss a partial extension to multiple roots.

We consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) graph G with m edges, n vertices and nonnegative edge weights. In this problem, a {0, 1} (−1,0,1}) incidence vector is associated with each cycle and the vector space over F 2 (Q) generated by these vectors is the cycle space of G . A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G . Cycle bases of low weight are useful in a number of contexts, for example, the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. There exists a set of Θ( mn ) cycles which is guaranteed to contain a minimum cycle basis. A minimum basis can be extracted by Gaussian elimination. The resulting algorithm [Horton 1987] was the first polynomial-time algorithm. Faster and more complicated algorithms have been found since then. We present a very simple method for extracting a minimum cycle basis from the candidate set with running time O ( m 2 n ), which improves the running time for sparse graphs. Furthermore, in the undirected case by using bit-packing we improve the running time also in the case of dense graphs. For undirected graphs we derive an O ( m 2 n /log n + n 2 m ) algorithm. For directed graphs we get an O ( m 3 n ) deterministic and an O ( m 2 n ) randomized algorithm. Our results improve the running times of both exact and approximate algorithms. Finally, we derive a smaller candidate set with size in Ω( m ) ∩ O ( mn ).

We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over $\mathbb{F}_{2}$ generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(m ω n), where ω is the best exponent of matrix multiplication. It is presently known that ω<2.376. We exhibit an O(m 2 n+mn 2log n) algorithm. When the edge weights are integers, we have an O(m 2 n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m ω ) time. For any ε>0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((m ω /ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight.

We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have nonnegative weights. A cycle in this graph is actually a cycle in the underlying undirected graph with edges traversable in both directions. A $\{-1,0,1\}$ edge incidence vector is associated with each cycle: edges traversed by the cycle in the right direction get 1 and edges traversed in the opposite direction get $-1$. The vector space over $\mathbb{Q}$ generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for this vector space. We seek a cycle basis where the sum of weights of the cycles is minimum. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m edges and n vertices runs in $\tilde{O}(m^{\omega+1}n)$ time, where $\omega < 2.376$ is the exponent of matrix multiplication. We present an $O(m^3n+m^2n^2\log n)$ algorithm. We obtain our algorithm by using fast matrix multiplication over rings and an efficient extension of Dijkstra's algorithm to compute a shortest cycle in G whose dot product with a function on its edge set is nonzero. We also present a simple $O(m^2n+mn^2\log n)$ Monte Carlo algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied. In this problem a $\{0,1\}$ edge incidence vector is associated with each cycle and the vector space over $\mathbb{Z}_2$ generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in $O(m^2n + mn^2\log n)$ time and our randomized algorithm for directed graphs matches this running time.

We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving ties. We say that a matching M is popular if there is no matching $M'$ such that the number of applicants preferring $M'$ to M exceeds the number of applicants preferring M to $M'$. In this paper, we give the first polynomial-time algorithms to determine if an instance admits a popular matching and to find a largest such matching, if one exists. For the special case in which every preference list is strictly ordered (i.e., contains no ties), we give an $O(n + m)$ time algorithm, where n is the total number of applicants and posts and m is the total length of all of the preference lists. For the general case in which preference lists may contain ties, we give an $O(\sqrt{n}m)$ time algorithm.

An instance of the stable marriage problem is an undirected bipartite graph G = ( X ∪ W , E ) with linearly ordered adjacency lists with ties allowed in the ordering. A matching M is a set of edges, no two of which share an endpoint. An edge e = ( a , b ) ∈ E ∖ M is a blocking edge for M if a is either unmatched or strictly prefers b to its partner in M , and b is unmatched, strictly prefers a to its partner in M , or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We give an O ( nm ) algorithm for computing strongly stable matchings, where n is the number of vertices and m the number of edges. The previous best algorithm had running time O ( m 2 ). We also study this problem in the hospitals-residents setting, which is a many-to-one extension of the aforementioned problem. We give an O ( m ∑ h∈H p h ) algorithm for computing a strongly stable matching in the hospitals-residents problem, where p h is the quota of a hospital h . The previous best algorithm had running time O ( m 2 ).

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs, and for a few other related problems. Previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. We show that our certificates of nonmembership can be authenticated in O(|V|) time.

Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [2003].We give an algorithm to compute a rank-maximal matching with running time O (min( n + C , C √ n ) m ), where C is the maximal rank of an edge used in a rank-maximal matching, n is the number of applicants and posts and m is the total size of the preference lists.

Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k -th root operations for integral k , and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real .

An instance of the curve reconstruction problem is a finite sample set V of an unknown collection of curves $\gamma$. The task is to connect the points in V in the order in which they lie on $\gamma$. Giesen [Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SCG '99), 1999, pp. 207--216] showed recently that the traveling salesman tourof V solves the reconstruction problem for single closed curves under otherwise weak assumptions on $\gamma$ and V; $\gamma$ must be a single closed curve. We extend his result along several directions: we weaken the assumptions on the sample; we show that traveling salesman-based reconstruction also works for single open curves (with and without specified endpoints) and for collections of closed curves; we give alternative proofs; and we show that in the context of curve reconstruction, the traveling salesman tour can be constructed in polynomial time.

Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify the natural fragment of normal dominance constraints and show that its satisfiability problem is in deterministic polynomial time.

In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the exact number types provided by LEDA allowing for efficient and exact computation with rational and algebraic geometric objects. It is the first kernel design which uses floating-point filter techniques on the level of geometric constructions. The experiments we present -- partly using the CGAL framework -- show a great improvement in speed and -- maybe even more important for practical applications -- memory consumption when dealing with more complex geometric computations.

We show that the combination of the CGAL framework for geometric computation and the number type ledareal yields easy-to-write, correct and efficient geometric programs.

Article Curve reconstruction: connecting dots with good reason Share on Authors: Tamal K. Dey Department of CSE, IIT Kharagpur, India 721302 Department of CSE, IIT Kharagpur, India 721302View Profile , Kurt Mehlhorn Max-Planck-Institut für Informatik, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, D-66123 Saarbrücken, GermanyView Profile , Edgar A. Ramos Max-Planck-Institut für Informatik, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, D-66123 Saarbrücken, GermanyView Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 197–206https://doi.org/10.1145/304893.304972Online:13 June 1999Publication History 33citation434DownloadsMetricsTotal Citations33Total Downloads434Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A program checker verifies that a particular program execution is correct. We give simple and efficient program checkers for some basic geometric tasks. We report about our experiences with program checking in the context of the LEDA system. We discuss program checking for data structures that have to rely on user-provided functions.

We show that the well-known random incremental constructlon of Clarkson and Shor [14] can be adapted via gradations to provide efficient external-memory algorithms for some geomctric problems.In particular, as the main result, we obtain an optimal randomized algorithm for the problem of computing the trapezoidal decomposition determined by a set of N line scgmcnts in the plane with K pairwise intersections, that requires G($$ logMjB Q + 5) expected disk accesses (I/OS), where M is the size of the available internal memory and B is the size of the block transfer.The approach is sufficiently general to obtain algorithms for the problems of 2-d and 3-d convex hulls, 2-d abstract Voronoi diagrams and batched point location in a planar subdivision, which require an optimal expected number of I/OS and are olmplcr than the ones previously known.The results extend to a external-memory model with multiple disks.

In this paper we describe and discuss a kernel for higher-dimensional computational geometry and we present its application in the calculation of convex hulls and delaunay triangulations.We introduce the basic data types like points, vectors, directions, hyperplanes, segments, rays, lines, spheres, affine transformations, and operations connecting these types.The description consists of a motivation for the basic class layout as well as topics like layered software design, runtime correctness via checking routines and documentation issues.Finally we shortly describe the usage of the kernel in the application domain.

Combinatorial and geometric computing is a core area of computer science (CS). In fact, most CS curricula contain a course in data structures and algorithms. The area deals with objects such as graphs, sequences, dictionaries, trees, shortest paths, flows, matchings, points, segments, lines, convex hulls, and Voronoi diagrams and forms the basis for application areas such as discrete optimization, scheduling, traffic control, CAD, and graphics. There is no standard library of the data structures and algorithms of combinatorial and geometric computing. This is in sharp contrast to many other areas of computing. There are, for example, packages in statistics (SPSS), numerical analysis (LINPACK, EISPACK), symbolic computation (MAPLE, MATHEMATICA), and linear programming (CPLEX).

We consider a branch-and-cut approach for solving the multiple sequence alignment problem, which is a central problem in computational biology. We propose a general model for this problem in which arbitrary gap costs are allowed. An interesting aspect of our approach is that the three (exponentially large) classes of natural valid inequalities that we consider turn out to be both facet-defining for the convex hull of integer solutions and separable in polynomial time. Both the proofs that these classes of valid inequalities are facet-defining and the description of the separation algorithms are far from trivial. Experimental results on several benchmark instances show that our method outperforms the best tools developed so far, in that it produces alignments that are better from a biological point of view. A noteworthy outcome of the results is the effectiveness of using branch-and-cut with only a carefully-selected subset of the variables as a heuristic.

A program checker verifies that a particular program execution is correct.We give simple and efficient program checkers for some basic geometric tasks.We report about our experiences with program checking in the context of the LEDA system.We discuss program checking for data structures that have to rely on userprovided functions.

We show that a maximum flow in a network with n vertices can be computed deterministically in $O({{n^3 } / {\log n}})$ time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of $O(n^3 )$. The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs. The number of operations executed on flow variables is $O(n^{{8 / 3}} (\log n)^{{4 / 3}} )$, in contrast with $\Omega (nm)$ flow operations for all previous algorithms, where m denotes the number of edges in the network. A randomized version of our algorithm executes $O(n^{{3 / 2}} m^{{1 / 2}} \log n + {{n^2 (\log n)^2 } / {\log }}(2 + {{n(\log n)^2 } / m})$ flow operations with high probability. For the special case in which all capacities are integers bounded by U, we show that a maximum flow can be computed deterministically using $O(n^{{3 / 2}} m^{{1 / 2}} + n^2 (\log U)^{{1 / 2}} + \log U$ flow operations and $O(\min \{ {{nm,n^3 } / {\log n\} + n^2 }}(\log U)^{{1 / 2}} + \log U)$ time. We finally argue that several of our results yield parallel algorithms with optimal speedup.

No abstract available.

The paper considers the problem of finding edge-disjoint paths between pairs of vertices in a finite grid graph. The homotopy class for each path to be routed is prespecified. A very fast algorithm that guarantees to find a solution for any solvable homotopic routing problem is given.

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time Ω(n2) where n is the number of obstacle corners. We introduce the tightness of a motion planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with running time ο((a/b · 1/ε crit + 1)n(log n)2), where a ≥ b are the lengths of the sides of a rectangle and εcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary of n bow-ties (c.f. Figure 1.1) is Ο(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.

For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... <-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)<-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.

The classification of polygons is considered in which two polygons are regularly equivalent if one can be continuously transformed into the other such that for each intermediate polygon, no two adjacent edges overlap. A discrete analogue of the classic Whitney–Graustein theorem is proven by showing that the winding number of polygons is a complete invariant for this classification. Moreover, this proof is constructive in that for any pair of equivalent polygons, it produces some sequence of regular transformations taking one polygon to the other. Although this sequence has a quadratic number of transformations, it can be described and computed in real time.

Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap , is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C , a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O ( m + n log C ). A two-level form of radix heap gives a bound of O ( m + n log C /log log C ). A combination of a radix heap and a previously known data structure called a Fibonacci heap gives a bound of O ( m + n a @@@@log C ). The best previously known bounds are O ( m + n log n ) using Fibonacci heaps alone and O ( m log log C ) using the priority queue structure of Van Emde Boas et al. [ 17].

A game on trees that is related to the dictionary problem is considered. There are two players, A and B, which take turns. Player A models the user of the dictionary and player B models the implementation of it. At his turn, player A modifies the tree by adding new leaves and player B modifies the tree by replacing subtrees. The cost of an insertion is the depth of the new leaf, and the cost of an update is the size of the subtree replaced. The goal of player A is to maximize cost and the goal of B is to minimize it. It is shown that there is a strategy for player A, which forces a cost of $\Omega (n \log \log n)$ for an n-game, i.e., a game in which each player takes n turns, and that there is a strategy for player B, which keeps the cost within $O(n \log \log n)$.

The work of F.M. Maley (Proc. Chapel Hill Conf. on VLSI, p.261-83, 1985) on \none-dimensional compaction with automatic jog insertion is refined. More \nprecisely, an algorithm with running time O((n2+k)log n), where k=O(n3) is a \nquantity which measures the difference between the input and output sketch, is \ngiven, and Maley's O(n4) algorithm is improved. The compaction algorithm takes \nas input a layout sketch, the wires in a layout sketch are flexible and only \nindicate the topology of the layout. The compactor minimizes the horizontal \nwidth of the layout while maintaining its routability. The exact geometry of \nthe wires is filled in by a router after compaction

A compacter takes as input a VLSI layout and produces as output an equivalent layout of smaller area. An effective compaction system frees the designer from the details of the design rules, and hence, increases his or her productivity and on the other hand produces high quality layouts. A general framework for compaction on a torus is introduced. This problem comes up whenever an array of identical cells has to compacted. The framework is instantiated by several specific compaction algorithms: one-dimensional compaction without and with automatic job insertion and two-dimensional compaction.>

A game on trees, which is related to the dictionary problem is considered. There are two players A and B who take turns. Player A models the user of the dictionary, and player B models its implementation. Player A modifies the tree by adding new leaves, and player B modifies the tree by replacing subtrees. The cost of an insertion is the depth of the new leaf, and the cost of an update is the size of the subtree replaced. The goal of player A is to maximize cost, and the goal of B is to minimize it. It is shown that there is a strategy for player A that forces a cost of Omega (n log log n) for an n-game, that is, a game consisting of n turns of both players, and a strategy for player B that keeps the cost in O(n log log n).>

VLSI designs for Galois field multipliers, which are central in many encoding and decoding procedures for error-detecting and error-correcting codes, are presented. An AT/sup 2/-optimal Galois-field multiplier based on AT/sup 2/-optimal integer multipliers for a synchronous VLSI model is exhibited. Galois field multiplication is done in two steps. First two polynomials (of degree n-1) over Z/sub p/ are multiplied, and then the resulting polynomial is reduced modulo a fixed irreducible polynomial (of degree n). Multiplication of polynomials is done by discrete Fourier transform (DFT). For p=2, the procedure is more involved for Z/sub p/(x) than for Z(x). An extension to the case of variable p is included and some open problems are stated.>

We give an Ο(n3·log n) time and Ο(n3) space algorithm for the continuous homotopic one layer routing problem. The main contribution is an extension of the sweep paradigm to a universal cover space of the plane.

A randomized algorithm is given for the dictionary problem with O(1) worst-case time for lookup and O(1) amortized expected time for insertion and deletion. An Omega (log n) lower bound is proved for the amortized worst-case time complexity of any deterministic algorithm in a class of algorithms encompassing realistic hashing-based schemes. If the worst-case lookup time is restricted to k, then the lower bound for insertion becomes Omega (kn/sup 1/k/).>

No abstract available.

We prove a Θ(log log n ) (i.e. matching upper and lower) bound on the complexity of the Union-Split-Find problem, a variant of the Union-Find problem. Our lower bound holds for all pointer machine algorithms and does not require the separation assumption used in the lower bound arguments of Tarjan [T79] and Blum [B86]. We complement this with a Θ(log n ) bound for the Split-Find problem under the separation assumption. This shows that the separation assumption can imply an exponential loss in efficiency.

We describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM’s shared memory is polynomial in n, each PRAM step is simulated by $O(\log n)$ MPC steps or by $O((\log n)^2 )$ steps of the bounded-degree network.This improves upon a previous result by Upfal and Wigderson. We also prove an $\Omega ({{(\log n)^2 } / {\log \log n}})$ lower bound on the number of steps needed to simulate one PRAM step on a bounded-degree network under the assumption that the communication in the network is point to point. As an important part of the simulation of PRAMs on MPCs, we use a new technique for dynamically averaging out a given work load among a set of processors operating in parallel.

In this paper an O ( N log N ) algorithm for routing through a rectangle is presented. Consider an n -by- m rectangular grid and a set of N two-terminal nets. A net is a pair of points on the boundary of the rectangle. A layout is a set of edge-disjoint paths, one for each net. Our algorithm constructs a layout, if there is one, in O ( N log N ) time; this contrasts favorably with the area of the layout that might be as large as N 2 . The layout constructed can be wired using four layers of interconnect with only O ( N ) contact cuts. A partial extension to multiterminal nets is also discussed.

We analyse the amortized behavior of AVL-trees under sequences of insertions. We show that the total rebalancing cost (=balance changes) for a sequence of n arbitrary insertions is at most $2.618n$. For random insertions the bound is improved to $2.26n$. We also show that the probability that t or more balance changes are required decreases exponentially with t.

Article Free Access Share on Dynamization of geometric data structures Authors: O. Fries Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West Germany Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West GermanyView Profile , K. Mehlhorn Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West Germany Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West GermanyView Profile , St. Näher Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West Germany Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West GermanyView Profile Authors Info & Claims SCG '85: Proceedings of the first annual symposium on Computational geometryJune 1985 Pages 168–176https://doi.org/10.1145/323233.323256Published:01 June 1985Publication History 24citation262DownloadsMetricsTotal Citations24Total Downloads262Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

For a Jordan curve C in the plane, let x_{1},x_{2},...,x_{n} be the abscissas of the intersection points of C with the x-axis, listed in the order the points occur on C. We call x_{1},x_{2},...,x_{n} a Jordan sequence. In this paper we describe an O(n)-time algorithm for recognizing and sorting Jordan sequences. The problem of sorting such sequences arises in computational geometry and computational geography. Our algorithm is based on a reduction of the recognition and sorting problem to a list-splitting problem. To solve the list-splitting problem we use level linked search trees.

A “semisorted table” is a one-dimensional array containing n data, which are not necessarily sorted, but can appear in p different permutations of the ascending order. We consider the problem of searching in such a table without knowing, in which one of the p permutations the data are stored (SST). It is shown that any deterministic search algorithm for SST needs at least $\sqrt[n]{p}$ comparisons in the worst case. This lower bound is generalized to average case performance even for nondeterministic algorithms. Some examples are given where the lower bound is tight.

According to VLSI theory, [log n, √n]is the range of computation times for which there may exist an AT2-optimal multiplier of n-bit integers. Such networks were previously known for the time range [Ω(log2 n), O(√n)]; this theoretical question is settled, by exhibition of a class of AT2-optimal multipliers with computation times [Ω(log n), O(√n)]. The designs are based on the DFT on a Fermat ring, whose elements are represented in a redundant radix-4 form to ensure O(1) addition time.

Let S(n) be a nice space bound such that log2 n S(n) n. Then every DCFL is recognized by a multitape Turing machine simultaneously in time O(n2/S(n)) and space O(S(n)), and this time bound is optimal. If the machine is allowed a random access input, then the time bound can be improved so that the time-space product is O(n1 + ).

An embedding of the graph G in the graph H is a one-to-one association of the vertices of G with the vertices of H.There are two natural measures of the cost of a graph embedding, namely, the dilationcost of the embedding: the maximum distance in H between the images of vertices that are adjacent in G; and the expansion-cost of the embedding: the ratio of the size of H to the size of G.The main results of this paper illustrate three situaUons wherein one of these costs can be minimized only at the expense of a dramatic increase in the other cost.The first result establishes the following: There is an embedding of n-node complete ternary trees in complete binary trees with dilation-cost 2 and expansion cost O(n~), where ~ = 1og3(4/3); but any embedding of these ternary trees in binary trees that has expansion-cost c < 2 must have dilation-cost G(logloglogn).The second result provides a stronger but less easily stated example of the same type of trade-off.The third result concerns generic binary trees, that is, complete binary trees into which all n-node binary trees are "efficiently" embeddable.There is a generic binary tree into which all n-node binary trees are embeddable with dilauon-cost O(1) and expansion-cost O(n ~) for some fixed constant c; if one insists on embeddings whose dilation-cost is exactly 1, then these embeddings must have expansion-cost f~(n¢~°*~)/~); tf one insists on embeddmgs whose expansion-cost is less than 2, then these embeddings must have dilation cost ~(log log log n) An interesting application of the polynomial size genenc binary tree m the first part of this three-part result is to yield simplified proofs of several results concerning computational systems with an intrinsic nouon of "computation tree," such as alternating and nondeterministic Turing machines and context-free grammars.

We address the question of program size of of perfect and universal hash functions. We prove matching upper and lower bounds (up to constant factors) on program size. Furthermore, we show that minimum or nearly minimum size programs can be found efficiently. In addition, these (near) minimum size programs have time complexity at most O(log* N) where N is the size of the universe in the case of perfect hashing, and time complexity 0(1) in the case of universal hashing. Thus for universal hashing programs of minimal size and minimal time complexity have been found.

In this paper we describe a new method for proving lower bounds on the complexity of VLSI - computations and more generally distributed computations. Lipton and Sedgewick observed that the crossing sequence arguments used to prove lower bounds in VLSI (or TM or distributed computing) apply to (accepting) nondeterministic computations as well as to deterministic computations. Hence whenever a boolean function f is such that f and -&-fmarc; (the complement of f, -&-fmarc; -&-equil; 1 -&-minus; f) have efficient nondeterministic chips then the known techniques are of no help for proving lower bounds on the complexity of deterministic chips. In this paper we describe a lower bound technique (Thm 1) which only applies to deterministic computations

We describe a fringe analysis of AVL-trees (and 2-3-trees and HB-trees) under random insertions and deletions. Previously, only the case of random insertions was dealt with.

The construction of alphabetic prefix codes with unequal letter costs and unequal probabilities is considered.A variant of the noiseless coding theorem is proved giving closely matching lower and upper bounds for the cost of the optimal code.An algorithm is described which constructs a nearly optimal code in linear time. KEY WORDS AND PHRASES;

A new algorithm is presented for constructing nearly optimal prefix codes in the case of unequal letter costs and unequal probabilities. A bound on the maximal deviation from the optimum is derived and numerical examples are given. The algorithm has running timeO(t \cdot n), wheretis the number of letters andnis the number of probabilities.

We consider search trees under time-varying access probabilities. Let $S = \{ B_1 , \cdots ,B_n \} $ and let $p_i^t $ be the number of accesses to object $B_i $ up to time t, $W^t = \sum {p_i^t } $. We introduce D-trees with the following properties. 1) A search for $X = B_i $ at time t takes time $O(\log W^t /p_i^t )$. This is nearly optimal. 2) Update time after a search is at most proportional to search time, i.e. the overhead for administration is small.

The weighted path length of optimum binary search trees is bounded above by $\sum \beta_i + 2\sum \alpha_j + H$ where H is the entropy of the frequency distribution, $\sum \beta _i $ is the total weight of the internal nodes, and $\sum \alpha_j$ is the total weight of the leaves. This bound is best possible. A linear time algorithm for constructing nearly optimal trees is described.

We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of these classes are investigated. Honest polynomial classes are generated by running time. They posses a modified Ritchie-Cobham property. A polynomial class is a complexity class iff it is honest.