Abstract Motivated by recent insights into the online bipartite matching problem ( OBM ), our goal was to extend the optimal algorithm for it, namely Ranking , all the way to the special case of adwords problem, called Small , in which bids are small compared to budgets; the latter has been of considerable practical significance in ad auctions (Mehta et al. in J. ACM (JACM) 54:22-es, 2007). This approach would yield a budget-oblivious algorithm , i.e., the algorithm would not need to know budgets of advertisers and therefore could be used in autobidding platforms. We present such an algorithm for Single-Valued , a special case of Small . However, an extension to Small failed because of failure of the No-Surpassing Property . Since the probabilistic ideas underlying our algorithm are quite substantial, we have stated them formally, after assuming the No-Surpassing Property, and we leave the open problem of removing this assumption.

We study the classical rent division problem, where n agents must allocate n indivisible rooms and split a fixed total rent R. The goal is to compute an envy-free (EF) allocation, where no agent prefers another agent’s room and rent to their own. This problem has been extensively studied under standard assumptions, where efficient algorithms for computing EF allocations are known. We extend this framework by introducing two practically motivated constraints: (i) lower and upper bounds on room rents, and (ii) room-specific budget for agents. We develop efficient combinatorial algorithms that either compute a feasible EF allocation or certify infeasibility. We further design algorithms to optimize over EF allocations using natural fairness objectives such as maximin utility, leximin utility, and minimum utility spread. Our approach unifies both constraint types within a single algorithmic framework, advancing the applicability of fair division methods in real-world platforms such as Spliddit.

Abstract. In 1979, Hylland and Zeckhauser [ J. Polit. Econ., 87 (1979), pp. 293–314] gave a simple and general mechanism for a one-sided matching market, given cardinal utilities of agents over goods. They use the power of a pricing mechanism, which endows their mechanism with several desirable properties—it produces an allocation that is Pareto optimal and envy free, and the mechanism is incentive compatible in the large. It therefore provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to characterize the computational complexity of this mechanism. We present the following results: (1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., [Formula: see text] utilities, and more generally, when each agent’s utilities come from a bivalued set. (2) An example that has only irrational equilibria; hence this problem is not in PPAD. (3) A proof of membership of the problem in the class FIXP; as a corollary we get that a Hylland–Zeckhauser (HZ) equilibrium can always be expressed via algebraic numbers. For this purpose, we give a new proof of the existence of an HZ equilibrium using Brouwer’s fixed point theorem; the proof of Hylland and Zeckhauser used Kakutani’s fixed point theorem, which is more involved. (4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. In subsequent work [T. Chen et al., SODA 2022, SIAM, Philadelphia, pp. 2253–2268], the problem of computing an approximate HZ equilibrium was shown to be PPAD-hard, thereby establishing it to be PPAD-complete. We leave open the (difficult) question of determining if computing an exact HZ equilibrium is FIXP-hard. We also give pointers to the substantial body of work on cardinal-utility matching markets which followed [V. V. Vazirani and M. Yannakakis, LIPIcs. Leibniz Int. Proc. Inform. 185, Schloss Dagstuhl, Wadern Germany, 59].

In a one-sided matching market, we are given a set G of goods and a set A of agents with |A| = |G|. Agents have preferences over the goods and each agent is to be assigned exactly one good. The goal is to design a mechanism without monetary transfers which finds a perfect matching satisfying desirable game-theoretic properties. Markets of this kind arise in many scenarios where payments are impractical or immoral such as when assigning students to schools or doctors to hospitals.

In a recent paper, Beniamini and Nisan [4] gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph G⊆Kn,n has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary weight function w on the edges of Kn,n, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph G⊆Kn,n contains one of these minimum weight perfect matchings. Finally, we discuss a number of open problems which follow from [4] and our work; in particular, extending the main theorem of [4] to non-bipartite graphs.

This paper addresses two deficiencies of models in the area of matching-based market design. The first arises from the recent realization that the most prominent solution that uses cardinal utilities, namely the Hylland-Zeckhauser (HZ) mechanism, is intractable; computation of even an approximate equilibrium is PPAD-complete. The second is the extreme paucity of models that use cardinal utilities. Our paper addresses both these issues by proposing Nash-bargaining-based matching market models. Since the Nash bargaining solution is captured by a convex program, efficiency follows. In addition, it possesses several desirable game-theoretic properties. Our approach yields a rich collection of models: for one-sided as well as two-sided markets, for Fisher as well as Arrow-Debreu settings, and for a wide range of utility functions, all the way from linear to Leontief. We give very fast implementations for these models using Frank-Wolfe and Cutting Plane algorithms. These help solve large instances with several thousand agents and goods in a matter of minutes on a PC, even for a one-sided matching market under piecewise-linear concave utility functions and a two-sided matching market under linear utility functions. In contrast, using HZ, going beyond even $n = 10$ is prohibitive. Several new ideas were needed, beyond the standard methods, to obtain these implementations. In particular, we present several lower bounding schemes, which not only help improve the convergence of our solution methods but also shed light on fairness properties of the Nash-bargaining-based models.

In the classic Adwords problem introduced by Mehta et al.\ (2007), we have a bipartite graph between advertisers and queries. Each advertiser has a maximum budget that is known a priori. Queries are unknown a priori and arrive sequentially. When a query arrives, advertisers make bids and we (immediately and irrevocably) decide which (if any) Ad to display based on the bids and advertiser budgets. The winning advertiser for each query pays their bid up to their remaining budget. Our goal is to maximize total budget utilized without any foreknowledge of the arrival sequence (which could be adversarial). We consider the setting where the online algorithm does not know the advertisers' budgets a priori and the budget of an advertiser is revealed to the algorithm only when it is exceeded. A naïve greedy algorithm is 0.5 competitive for this setting and finding an algorithm with better performance remained an open problem. We show that no deterministic algorithm has competitive ratio better than 0.5 and give the first (randomized) algorithm with strictly better performance guarantee. We show that the competitive ratio of our algorithm is at least 0.522 but also strictly less than $(1-1/e)$. We present novel applications of budget oblivious algorithms in search ads and beyond. In particular, we show that our algorithm achieves the best possible performance guarantee for deterministic online matching in the presence of multi-channel traffic (Manshadi et al. (2022)).

In 1979, Hylland and Zeckhauser [Hylland and Zeckhauser, 1979] gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties - it is incentive compatible in the large and produces an allocation that is Pareto optimal - and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 utilities, and more generally, when each agent’s utilities come from a bi-valued set. 2) An example that has only irrational equilibria, hence proving that this problem is not in PPAD. 3) A proof of membership of the problem in the class FIXP. 4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. We leave open the (difficult) questions of determining if computing an exact HZ equilibrium is FIXP-hard and an approximate HZ equilibrium is PPAD-hard.

In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in $K_{3,3}$-minor-free graphs by building on Kasteleyn's scheme for planar graphs, and stated that this “opens up the possibility of obtaining an NC algorithm for finding a perfect matching in $K_{3,3}$-free graphs.” In this paper, we finally settle this 30-year-old open problem. Building on recent NC algorithms for planar and bounded-genus perfect matching by Anari and Vazirani and later by Sankowski, we obtain NC algorithms for perfect matching in any minor-closed graph family that forbids a one-crossing graph. This family includes several well-studied graph families including the $K_{3,3}$-minor-free graphs and $K_5$-minor-free graphs. Graphs in these families not only have unbounded genus, but can have genus as high as $O(n)$. Our method applies as well to several other problems related to perfect matching. In particular, we obtain NC algorithms for the following problems in any family of graphs (or networks) with a one-crossing forbidden minor: (1) Determining whether a given graph has a perfect matching and, if so, finding one. (2) Finding a minimum-weight perfect matching in the graph, assuming that the edge weights are polynomially bounded. (3) Finding a maximum $st$-flow in the network, with arbitrary capacities. The main new idea enabling our results is the definition and use of matching-mimicking networks, small replacement networks that behave the same with respect to matching problems involving a fixed set of terminals, as the larger network they replace.

We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted $\mathcal{R}_1$ and $\mathcal{R}_2$. In round $\mathcal{R}_1$, the capacity of each school is fixed and mechanism $\mathcal{M}_1$ finds a student optimal stable matching. In round $\mathcal{R}_2$, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results, the first simply disallows any re-allocations in round $\mathcal{R}_2$, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round $\mathcal{R}_2$ under certain settings.

Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of randomized NC matching algorithms [KUW85, MVV87]. Over the last five years, the theoretical computer science community has launched a relentless attack on this question, leading to the discovery of several powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum-weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem. We believe this new fact has qualitatively changed the nature of this open problem. All known efficient matching algorithms for general graphs follow one of two approaches: given by Edmonds [Edm65] and Lovász [Lov79]. Our oracle-based algorithm follows a new approach and uses many of the ideas discovered in the last five years. The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, recently Goldwasser and Grossman [GG15] gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits. A corollary of our reduction is an analogous algorithm for general graphs.

In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in K3,3-minor-free graphs by building on Kasteleyn's scheme for planar graphs, and stated that this "opens up the possibility of obtaining an NC algorithm for finding a perfect matching in K3,3-free graphs." In this paper, we finally settle this 30-year-old open problem. Building on recent NC algorithms for planar and bounded-genus perfect matching by Anari and Vazirani and by Sankowski, we obtain NC algorithms for perfect matching in any minor-closed graph family that forbids a one-crossing graph. This result applies to several well-studied graph families including the K3,3-minor-free graphs and K5-minor-free graphs. Graphs in these families not only have unbounded genus, but can have genus as high as O(n). Our method applies as well to several other problems related to perfect matching. In particular, we obtain NC algorithms for the following problems in any family of graphs (or networks) with a one-crossing forbidden minor: - Determining whether a given graph has a perfect matching and if so, finding one. - Finding a minimum weight perfect matching in the graph, assuming that the edge weights are polynomially bounded. - Computing the number of perfect matchings in the graph. - Finding a maximum st-flow in the network, with arbitrary capacities. The main new idea enabling our results is the definition and use of matching-mimicking networks, small replacement networks that behave the same, with respect to matching problems involving a fixed set of terminals, as the larger network they replace.

In this paper, we introduce the issue of finding solutions to the stable matching problem that are robust to errors in the input and we obtain the first algorithmic results on this topic. In the process, we also initiate work on a new structural question concerning the stable matching problem, namely finding relationships between the lattices of solutions of two "nearby" instances. Our main algorithmic result is the following: We identify a polynomially large class of errors, D, that can be introduced in a stable matching instance. Given an instance A of stable matching, let B be the instance that results after introducing one error from D, chosen via a discrete probability distribution. The problem is to find a stable matching for A that maximizes the probability of being stable for B as well. Via new structural properties of the type described in the question stated above, we give a polynomial time algorithm for this problem.

Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC perfect matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution. In this article, we give an NC algorithm for finding a perfect matching in a planar graph. Our algorithm uses the above-stated fact about counting perfect matchings in a crucial way. Our main new idea is an NC algorithm for finding a face of the perfect matching polytope at which a set (which could be polynomially large) of conditions, involving constraints of the polytope, are simultaneously satisfied. Several other ideas are also needed, such as finding, in NC, a point in the interior of the minimum-weight face of this polytope and finding a balanced tight odd set.

Negative frequency-dependent selection (i.e., declining fitness with increased frequency in the population) is thought to be one of the factors that maintains biological diversity. In this paper, we give a concrete mathematical argument supporting this. Our model is as follows: A collection of species derive their fitnesses via a rock-paper-scissors-type game whose precise payoffs are a function of the environment. The new aspect of our model lies in adding a feedback loop: the environment changes according to the relative fitnesses of the species (hence, payoffs change as a function of fitness, which in turn changes as a function of payoffs). The changes in the payoffs are in keeping with the principle of negative frequency-dependent selection, which is widespread in nature. In order to model our game as a continuous time dynamical system, we cast it in the setting of a differential game. We show that for certain parameters, this dynamics cycles, i.e., no species goes extinct and diversity is maintained. We believe that our techniques can be applied to optimization and machine learning to show that first order methods (e.g., gradient descent/ascent) do cycle even in online settings in which the loss function changes with time.

Recently Cole and Gkatzelis [10] gave the first constant factor approximation algorithm for the problem of allocating indivisible items to agents, under additive valuations, so as to maximize the Nash social welfare (NSW). We give constant factor algorithms for a substantial generalization of their problem – to the case of separable, piecewise-linear concave utility functions. We give two such algorithms, the first using market equilibria and the second using the theory of real stable polynomials. Both approaches require new algorithmic ideas.

We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling and communicating over a network. This model is quite different from the traditional models, to the extent that neither do the classical equilibrium existence results seem to apply to it nor do any of the efficient algorithmic techniques developed to compute equilibria. In particular, our model does not satisfy the condition of non-satiation, which is used critically to show the existence of equilibria in traditional market models and we observe that our set of equilibrium prices could be a connected, nonconvex set. We give a proof of the existence of equilibria and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. Finally, we show that our model inherits many of the fairness properties of traditional equilibrium models as well as new models, such as CEEI.

Sequence overlap graphs, constructed based on suffix-prefix relationships between pairs of sequences, are an important data structure in computational biology. High throughput sequencers can read several million to a few billion DNA fragments in a single experiment, making the construction of overlap graphs for such datasets compute-intensive. In this paper, we present a Locality-Sensitive Hashing based parallel heuristic algorithm to construct overlap graphs for large genomic datasets. With reasonable assumptions on the characteristics of input sequences, we establish probabilistic bounds on the quality of the overlap graphs so produced. We demonstrate the validity and efficiency of our approach by comparing against true overlap graphs using datasets derived from small (E. coli) and large (H. sapiens) genomes.

Inspired by the work of Kempe et al. [Kempe, Kleinberg, Oren, Slivkins, EC 2013], we introduce and analyze a model on opinion formation; the update rule of our dynamics is a simplified version of that of [Kempe, Kleinberg, Oren, Slivkins, EC 2013]. We assume that the population is partitioned into types whose interaction pattern is specified by a graph. Interaction leads to population mass moving from types of smaller mass to those of bigger mass. We show that starting uniformly at random over all population vectors on the simplex, our dynamics converges point-wise with probability one to an independent set. This settles an open problem of [Kempe, Kleinberg, Oren, Slivkins, EC 2013], as applicable to our dynamics. We believe that our techniques can be used to settle the open problem for the Kempe et al. dynamics as well. Next, we extend the model of Kempe et al. by introducing the notion of birth and death of types, with the interaction graph evolving appropriately. Birth of types is determined by a Bernoulli process and types die when their population mass is less than epsilon (a parameter). We show that if the births are infrequent, then there are long periods of "stability" in which there is no population mass that moves. Finally we show that even if births are frequent and "stability" is not attained, the total number of types does not explode: it remains logarithmic in 1/epsilon.

A new approach to understanding evolution [Val09], namely viewing it through the lens of computation, has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [CLPV14]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [WVA05], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability. On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game. Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.

No abstract available.

Our first result shows membership in PPAD for the problem of computing approximate equilibria for an Arrow-Debreu exchange market for piecewise-linear concave (PLC) utility functions. As a corollary we also obtain membership in PPAD for Leontief utility functions. This settles an open question of Vazirani and Yannakakis (2011).

We present a simple and natural non-pricing mechanism for allocating divisible goods among strategic agents having lexicographic preferences. Our mechanism has favorable properties of incentive compatibility (strategy-proofness), Pareto efficiency, envy-freeness, and time efficiency.

Using Lemke's scheme, we give a complementary pivot algorithm for computing an equilibrium for Arrow--Debreu markets under separable, piecewise-linear concave (SPLC) utilities. Despite the polynomial parity argument on directed graphs (PPAD) completeness of this case, experiments indicate that our algorithm is practical---on randomly generated instances, the number of iterations it needs is linear in the total number of segments (i.e., pieces) in all the utility functions specified in the input. Our paper settles a number of open problems: (1) Eaves (1976) gave an LCP formulation and a Lemke-type algorithm for the linear Arrow--Debreu model. We generalize both to the SPLC case, hence settling the relevant part of his open problem. (2) Our path following algorithm for SPLC markets, together with a result of Todd (1976), gives a direct proof of membership of such markets in PPAD and settles a question of Vazirani and Yannakakis (2011). (3) We settle a question of Devanur and Kannan (2008) of obtaining a “systematic way of finding equilibrium instead of the brute-force way” for the separable case and we obtain a strongly polynomial algorithm if the number of goods or agents is constant. (4) We give a combinatorial way of interpreting Eaves' algorithm for the linear case, hence answering Eaves' question (1976), “That the algorithm can be interpreted as a `global market adjustment mechanism' might be interesting to explore.”

Even though production is an integral part of the Arrow-Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. This paper takes a significant step towards understanding computational aspects of markets with production. For markets with separable, piecewise-linear concave (SPLC) utilities and SPLC production, we obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria, and we further give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975 [14]. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. We further give a proof of PPAD-hardness for this problem and also for its restriction to markets with linear utilities and SPLC production. Experiments show that our algorithm is practical. Also, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Finally, we show that an LCP-based approach cannot be extended to PLC (non-separable) production, by constructing an example which has only irrational equilibria.

After more than a decade of work in TCS on the computability of market equilibria, complementary pivot algorithms have emerged as the best hope of obtaining practical algorithms. So far they have been used for markets under separable, piecewise-linear concave (SPLC) utility functions [23] and SPLC production sets [25]. Can his approach extend to non-separable utility functions and production sets? A major impediment is rationality, i.e., if all parameters are set to rational numbers, there should be a rational equilibrium.

Motivated by the recent work of [V. V. Vazirani, J. ACM, 59 (2012), 7], we take a fresh look at understanding the quality and robustness of solutions to Nash and nonsymmetric bargaining games by subjecting them to several stress tests. Our tests are quite basic; e.g., we ask whether the solutions are computable in polynomial time, and whether they have certain properties such as efficiency, fairness, and desirable response when agents change their disagreement points or play with a subset of the agents. Our main conclusion is that imposing submodularity, a natural economies of scale condition, on Nash and nonsymmetric bargaining games endows them with several desirable properties.

Recent results establishing evidence of intractability for such restrictive utility functions as additively separable, piecewise-linear and concave, under both Fisher and Arrow--Debreu market models, have prompted the question of whether we have failed to capture some essential elements of real markets, which seem to do a good job of finding prices that maintain parity between supply and demand. The main point of this paper is to show that even nonseparable, concave utility functions can be handled efficiently in a suitably chosen, though natural, realistic, and useful, market model. Our model allows for perfect price discrimination, supports unique equilibrium prices, and satisfies both welfare theorems.

We introduce the notion of a rational convex program (RCP) and we classify the known RCPs into two classes: quadratic and logarithmic. The importance of rationality is that it opens up the possibility of computing an optimal solution to the program via an algorithm that is either combinatorial or uses an LP-oracle. Next, from the linear case of the Arrow-Debreu market model, we define a new Nash bargaining game, which we call ADNB. We show that the convex program for ADNB is a logarithmic RCP, but unlike other known members of this class, it is non-total. Our main result is a combinatorial, polynomial time algorithm for ADNB. It turns out that the reason for infeasibility of logarithmic RCPs is quite different from that for LPs and quadratic RCPs. Finally, we present a number of interesting questions that the new notion of RCP raises.

Using the powerful machinery of the linear complementarity problem and Lemke's algorithm, we give a practical algorithm for computing an equilibrium for Arrow-Debreu markets under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of this case. As a corollary, we obtain the first elementary proof of existence of equilibrium for this case, i.e., without using fixed point theorems. In 1975, Eaves [10] had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave utilities. Our result settles the relevant subcase of his problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm for SPLC markets, thereby giving a direct proof of membership of this case in PPAD.

We introduce the notion of a rational convex program (RCP) and we classify the known RCPs into two classes: quadratic and logarithmic. The importance of rationality is that it opens up the possibility of computing an optimal solution to the program via an algorithm that is either combinatorial or uses an LP-oracle. Next, we define a new Nash bargaining game, called ADNB, which is derived from the linear case of the Arrow-Debreu market model. We show that the convex program for ADNB is a logarithmic RCP, but unlike other known members of this class, it is nontotal. Our main result is a combinatorial, polynomial-time algorithm for ADNB. It turns out that the reason for infeasibility of logarithmic RCPs is quite different from that for LPs and quadratic RCPs. We believe that our ideas for surmounting the new difficulties will be useful for dealing with other nontotal RCPs as well. We give an application of our combinatorial algorithm for ADNB to an important “fair” throughput allocation problem on a wireless channel. Finally, we present a number of interesting questions that the new notion of RCP raises.

The solution to a Nash or a nonsymmetric bargaining game is obtained by maximizing a concave function over a convex set; i.e., it is the solution to a convex program. We show that each 2-player game whose convex program has linear constraints, admits a rational solution and such a solution can be found in polynomial time using only an LP solver. If, in addition, the game is succinct, i.e., the coefficients in its convex program are "small," then its solution can be found in strongly polynomial time. We also give nonsuccinct linear games whose solution can be found in strongly polynomial time.

ISPs are increasingly selling "tiered" contracts, which offer Internet connectivity to wholesale customers in bundles, at rates based on the cost of the links that the traffic in the bundle is traversing. Although providers have already begun to implement and deploy tiered pricing contracts, little is known about how to structure them. While contracts that sell connectivity on finer granularities improve market efficiency, they are also more costly for ISPs to implement and more difficult for customers to understand. Our goal is to analyze whether current tiered pricing practices in the wholesale transit market yield optimal profits for ISPs and whether better bundling strategies might exist. In the process, we deliver two contributions: 1) we develop a novel way of mapping traffic and topology data to a demand and cost model, and 2) we fit this model on three large real-world networks: an European transit ISP, a content distribution network, and an academic research network, and run counterfactuals to evaluate the effects of different bundling strategies. Our results show that the common ISP practice of structuring tiered contracts according to the cost of carrying the traffic flows (e.g., offering a discount for traffic that is local) can be suboptimal and that dividing contracts based on both traffic demand and the cost of carrying it into only three or four tiers yields near-optimal profit for the ISP.

We consider Fisher and Arrow--Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be written using polynomially many bits. There is no simple necessary and sufficient condition for the existence of an equilibrium: The problem of checking for existence of an equilibrium is NP-complete for both market models; the same holds for existence of an ε-approximate equilibrium, for ε = O ( n −5 ). Under standard (mild) sufficient conditions, the problem of finding an exact equilibrium is in PPAD for both market models. Finally, building on the techniques of Chen et al. [2009a] we prove that under these sufficient conditions, finding an equilibrium for Fisher markets is PPAD-hard.

Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84–106] introduced the class of Eisenberg–Gale (EG) markets. We study the structure of EG(2) markets, the class of EG markets with two agents. We prove that all markets in this class are rational, that is, they have rational equilibrium, and they admit strongly polynomial time algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial linear program (LP). This helps positively resolve the status of two markets left as open problems by Jain and Vazirani: the capacity allocation market in a directed graph with two source-sink pairs and the network coding market in a directed network with two sources. Our algorithms for solving the corresponding nonlinear convex programs are fundamentally different from those obtained by Jain and Vazirani; whereas they use the primal-dual schema, our main tool is binary search powered by the strong LP-duality theorem.

We consider the class of max-min and min-max optimization problems subject to a global budget constraint. We undertake a systematic algorithmic and complexity-theoretic study of such problems, which we call design problems. Every optimization problem leads to a natural design problem. Our main result uses techniques of Freund and Schapire [Games Econom. Behav., 29 (1999), pp. 79–103] from learning theory, and its generalizations, to show that for a large class of optimization problems, the design version is as easy as the optimization version. We also observe the relationship between max-min design problems and fractional packing problems. In particular, we obtain in a systematic fashion results about the fractional packing number of Steiner trees.

Today's Internet's routing paths are inefficient with respect to both connectivity and the market for interconnection. The former manifests itself via needlessly long paths, de-peering, etc. The latter arises because of a primitive market structure that results in unfulfilled demand and unused capacity. Today's networks make pairwise, myopic interconnection decisions based on business considerations that may not mirror considerations of the edge networks (or end systems) that would benefit from the existence of a particular interconnection. These bilateral contracts are also complex and difficult to enforce.

Network accounting, forensics, security, and performance monitoring applications often need to examine detailed traces from subsets of flows ("subpopulations"), where the application desires flexibility in specifying the subpopulation (e.g., to detect a portscan, the application must observe many packets between a source and a destination with one packet to each port). However, the dynamism and volume of network traffic on many high-speed links necessitates traffic sampling, which adversely affects subpopulation monitoring: because many subpopulations of interest to operators are low-volume flows, conventional sampling schemes (e.g., uniform random sampling) miss much of the subpopulation's traffic. Today's routers and network devices provide scant support for monitoring specific traffic subpopulations.

We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal--dual paradigm in the enhanced setting of KKT conditions and convex programs. We pinpoint the added difficulty raised by this setting and the manner in which our algorithm circumvents it.

We present an improved “cooling schedule” for simulated annealing algorithms for combinatorial counting problems. Under our new schedule the rate of cooling accelerates as the temperature decreases. Thus, fewer intermediate temperatures are needed as the simulated annealing algorithm moves from the high temperature (easy region) to the low temperature (difficult region). We present applications of our technique to colorings and the permanent (perfect matchings of bipartite graphs). Moreover, for the permanent, we improve the analysis of the Markov chain underlying the simulated annealing algorithm. This improved analysis, combined with the faster cooling schedule, results in an $O(n^7\log^4{n})$ time algorithm for approximating the permanent of a $0/1$ matrix.

Perhaps the strongest notion of truth-revealing in a cost sharing mechanism is group strategyproofness. However, matters are not so clear-cut on fairness, and many different, sometimes even conflicting, notions of fairness have been proposed which have relevance in different situations. We present a large class of group strategyproof cost sharing methods, for submodular cost functions, satisfying a wide range of fairness criteria, thereby allowing the service provider to choose a method that best satisfies the notion of fairness that is most relevant to its application. Our class includes the Dutta–Ray egalitarian method as a special case. It also includes a new cost sharing method, which we call the opportunity egalitarian method.

We define a new class of markets, the Eisenberg-Gale markets. This class contains Fisher's linear market, markets from the resource allocation framework of Kelly kelly, as well as numerous interesting new markets.We obtain combinatorial, strongly polynomial algorithms for severalmarkets in this class.

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1−1/ e for this problem.

Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, so far this conjecture could not be verified even for the simple network consisting of K3,2with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network.

Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, this conjecture could not so far be verified even for the simple network consisting of K/sub 3,2/ with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network.

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive two optimal algorithms achieving competitive ratios of 1-1/e for this problem.

Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, this conjecture could not so far be verified even for the simple network consisting of K3,2with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network

In the digital goods setting we prove that for any randomized auction which is truthful in expectation, there exists an equivalent randomized auction which randomizes over truthful deterministic auctions. By equivalent auctions we mean auctions in which the probability of winning and the expected price offered are the same for all bidders for all bid values. We also prove an approximate equivalence proof in the case where the bids come from a discrete space. Finally, we consider the computational issue of finding an efficient equivalent auction.

Strategyproof cost-sharing mechanisms, lying in the core, that recover 1/α fraction of the cost, are presented for the set cover and facility location games; α = O(log n) for the former and 1.861 for the latter. Our mechanisms utilize approximation algorithms for these problems based on the method of dual-fitting.

No abstract available.

We describe a fixed point approach for the following stochastic optimization problem: given a multicast tree and probability distributions of user utilities, compute prices to offer the users in order to maximize the expected profit of the service provider. We show that any optimum pricing is a fixed point of an efficiently computable map. In the language of classical numerical analysis, we show that the non-linear Jacobi and Gauss-Seidel methods of coordinate descent are applicable to this problem. We provide proof of convergence to the optimum prices for special cases of utility distributions and tree edge costs.

Consider the following stochastic process executed on a graph G=(V,E) whose nodes are initially uncovered. In each step, pick a node at random and if it is uncovered, cover it. Otherwise, if it has an uncovered neighbor, cover a random uncovered neighbor. Else, do nothing. This can be viewed as a structured coupon collector process. We show that for a large family of graphs, O(n) steps suffice to cover all nodes of the graph with high probability, where n is the number of vertices. Among these graphs are d-regular graphs with d =Ω(log n log log n), random d-regular graphs with d =Ω(log n) and the k-dimensional hypercube where n=2k.This process arises naturally in answering a question on load balancing in peer-to-peer networks. We consider a distributed hash table in which keys are partitioned across a set of processors, and we assume that the number of processors grows dynamically, starting with a single processor. If at some stage there are n processors, the number of queries required to find a key is log2 n+O(1), the number of pointers maintained by each processor is log2 n+O(1), and moreover the worst ratio between the loads of processors is O(1), with high probability. To the best of our knowledge, this is the first analysis of a distributed hash table that achieves asymptotically optimal load balance, while still requiring only O(log n) pointers per processor and O(log n) queries for locating a key; previous methods required Ω(log2 n) pointers per processor and Ω(log n) queries for locating a key.

In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O ( m log m ) and O ( n 3 ), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.

Although the study of market equilibria has occupied center stage within mathematical economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We provide the first such algorithm for the linear version of a problem defined by Irving Fisher in 1891. Our algorithm is modeled after Kuhn's (1995) primal-dual algorithm for bipartite matching.

Perhaps the strongest notion of truth-revealing in a cost sharing method is group strategyproofness. However, matters are not so clear-cut on fairness, and many different, sometimes even conflicting, notions of fairness have been proposed which have relevance in different situations. We present a large class of group strategyproof cost sharing methods, for submodular cost functions, satisfying a wide range of fairness criteria, thereby allowing the service provider to choose a method that best satisfies the notion of fairness that is most relevant to her application. Our class includes the Dutta-Ray egalitarian method as a special case. It also includes a new cost sharing method, which we call the opportunity egalitarian method.

The Internet, which is intrinsically a common playground for a large number of players with varying degrees of collab-orative and selsh motives, naturally gives rise to numerous new game theoretic issues. Computational problems under-

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k -median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m ) and O(m log m(L + log ( n ))) respectively, where n and m are the total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms.

The minimum rectilinear Steiner tree (RST) problem is one of the fundamental problems in the field of electronic design automation. The problem is NP-hard, and much work has been devoted to designing good heuristics and approximation algorithms; to date, the champion in solution quality among RST heuristics is the Batched Iterated 1-Steiner (BI1S) heuristic of Kahng and Robins. In a recent development, exact RST algorithms have witnessed spectacular progress: The new release of the GeoSteiner code of Warme et al. has average running time comparable to that of the fastest available BI1S implementation, due to Robins. We are, thus, faced with the paradoxical situation that an exact algorithm for an NP-hard problem is competitive in speed with a state of-the-art heuristic for the problem. The main contribution of this paper is a new RST heuristic, which has at its core a recent 3/2 approximation algorithm of Rajagopalan and Vazirani for the metric Steiner tree problem on quasi-bipartite graphs-these are graphs that do not contain edges connecting pairs of Steiner vertices. The RV algorithm is built around the linear programming relaxation of a sophisticated integer program formulation, called the bidirected cut relaxation. Our heuristic achieves a good running time by combining an efficient implementation of the RV algorithm with simple, but powerful geometric reductions. Experiments conducted on both random and real very large scale integrated instances show that the new RST heuristic runs significantly faster than Robins' implementation of BI1S and than the GeoSteiner code. Moreover, the new heuristic typically gives higher-quality solutions than BI1S.

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m) and O(m log m(L+log(n))) respectively, where n and m are the total number of vertices and edges in the underlying graph. The main algorithmic idea is a new extension of the primal-dual schema.

The minimum rectilinear Steiner tree (RST) problem is one of the fundamental problems in the field of electronic design automation. The problem is NP-hard, and much work has been devoted to designing good heuristics and approximation algorithms; to date, the champion in solution quality among RST heuristics is the Batched Iterated 1-Steiner (BI1S) heuristic of Kahng and Robins (1992). In a recent development, exact RST algorithms have witnessed spectacular progress: the new release of the GeoSteiner code of Warme, Winter, and Zachariasen (1998) has average running time comparable to that of the fastest available Bl1S implementation, due to Robins. We are thus faced with the paradoxical situation that an exact algorithm for an NP-hard problem is competitive in speed with a state-of-the-art heuristic for the problem. The main contribution of this paper is a new RST heuristic, which has at its core a recent 3/2 approximation algorithm of Rajagopalan and Vazirani (1999) for the metric Steiner tree problem on quasi-bipartite graphs-these are graphs that do not contain edges connecting pairs of Steiner vertices. The RV algorithm is built around the linear programming relaxation of a sophisticated integer program formulation, called the bidirected cut relaxation. Our heuristic achieves a good running time by combining an efficient implementation of the RV algorithm with simple, but powerful geometric reductions. Experiments conducted on both random and real VLSI instances show that the new RST heuristic runs significantly faster than Robins' implementation of BI1S and than the GeoSteiner code. Moreover, the new heuristic typically gives higher-quality solutions than Bl1S.

A key step in counting via sampling is constructing an onbiased estimator, X, for the parameter .9 in question, and proving a bound on its second moment, E(X').A key applacation of this method is to obtaining a FPRAS for a #Pcomplete problem; a FPRAS results if the ratio r = m EIW is polynamially bounded in the size of the input.We show that if no additional information is available about the dis tribution of X, then this condition is also necessary.The proof involves establishing a new optimality result in parametric statistics.We introduce the notion of a majorizing estimator, a very strict optimality requirement that we need for making wont-case (over inputs) and in-probability (of falling in the desired accuracy range of the parameter 8) statements.We show that for the problem of estimating the mean of a Gaussian distribution (from the variable-location, fixed-scale family {GB}), the sample mean is a majorizing estimator.An extension of this argument shows that the sample mean is an optimal estimator in every central moment among all estimators.To compare, the celebrated Cramer-Rae lower bound, applied to the family {CS}, establishes that the sample mean is the optimal estimator in mean square error among alI unbiased estimators.We fixther show that the mean estimator is the unique majorizing estimator for {Ge}.

A factor 2 approximation algorithm for the problem of finding a minimum-cost b-balanced cut in planar graphs is presented, for $b \leq {1 \over 3}$. We assume that the vertex weights are given in unary; for the case of binary vertex weights, a pseudoapproximation algorithm is presented. This problem is of considerable practical significance, especially in VLSI design. The natural algorithm for this problem accumulates sparsest cuts iteratively. One of our main ideas is to give a definition of sparsity, called net-sparsity, that reflects precisely the cost of the cuts accumulated by this algorithm. However, this definition is too precise: we believe it is NP-hard to compute a minimum--net-sparsity cut, even in planar graphs. The rest of our machinery is built to work with this definition and still make it computationally feasible. Toward this end, we use several ideas from the works of Rao [ Proceedings, 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 225--237; Proceedings, 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 229--240] and Park and Phillips [ Proceedings, 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 766--775].

We build on the classical greedy sequential set cover algorithm, in the spirit of the primal-dual schema, to obtain simple parallel approximation algorithms for the set cover problem and its generalizations. Our algorithms use randomization, and our randomized voting lemmas may be of independent interest. Fast parallel approximation algorithms were known before for set cover, thoughnot for the generalizations considered in this paper.

The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of trellis complexity are considered: the total number of states, the total number of edges, and the maximum state complexity of the trellis. The problem is proven NP-hard for all three measures, provided the field over which the code is specified is not fixed. We leave open the problem of dealing with the case of a fixed field, in particular GF(2).

We present an efficient algorithm for computing the minimal trellis for a group code over a finite Abelian group, given a generator matrix for the code. We also show how to compute a succinct representation of the minimal trellis for such a code, and present algorithms that use this information to efficiently compute local descriptions of the minimal trellis. This extends the work of Kschischang and Sorokine (1995), who handled the case of linear codes over fields. An important application of our algorithms is to the construction of minimal trellises for lattices. A key step in our work is handling codes over cyclic groups C/sub p//spl alpha/, where p is a prime. Such a code can be viewed as a submodule over the ring Z/sub p//spl alpha/. Because of the presence of zero-divisors in the ring, submodules do not share the useful properties of vector spaces. We get around this difficulty by restricting the notion of linear combination to p-linear combination, and introducing the notion of a p-generator sequence, which enjoys properties similar to that of a generator matrix for a vector space.

Consider the multicommodity flow problem in which the object is to maximize the sum of commodities routed. We prove the following approximate max-flow min-multicut theorem: \[ \frac{{\min {\text{multicut}}}}{{O(\log k)}} \leqslant \max {\text{flow}} \leqslant \min {\text{multicut}}, \] where k is the number of commodities. Our proof is constructive; it enables us to find a multicut within $O(\log k)$ of the max flow (and hence also the optimal multicut). In addition, the proof technique provides a unified framework in which one can also analyse the case of flows with specified demands of Leighton and Rao and Klein et al. and thereby obtain an improved bound for the latter problem.

We present an efficient algorithm for computing the minimal trellis for a group code over a finite abelian group, given a generator matrix for the code. We also show how to compute a succinct representation of the minimal trellis for such a code, and present algorithms that use this information to compute efficiently local descriptions of the minimal trellis. This extends the work of Kschischang and Sorokine (see ibid., vol.41, no.6, p.1926-37, 1995), who treated the case of linear codes over fields. An important application of our algorithms is to the construction of minimal trellises for lattices. A key step in our work is handling codes over cyclic groups C/sub p//spl alpha/, where p is a prime. Such a code can be viewed as a module over the ring Z/sub p//spl alpha/. Because of the presence of zero divisors in the ring, modules do not share the useful properties of vector spaces. We get around this difficulty by restricting the notion of linear combination to a p-linear combination, and by introducing the notion of a p-generator sequence, which enjoys properties similar to those of a generator matrix for a vector space.

Two simple approximation algorithms for the minimum k-cut problem are presented. Each algorithm finds a k cut having weight within a factor of $(2 - 2/k)$ of the optimal. One algorithm is particularly efficient—it requires a total of only $n - 1$ maximum flow computations for finding a set of near-optimal k cuts, one for each value of k between 2 and n.

Building on the works of S.B. Rao (1987, 1992) and J.K. Park and C.A. Phillips (1993), we present a factor 2 approximation algorithm for the problem of finding a minimum cost b-balanced cut in planar graphs, for b/spl les/1/3, if the vertex weights are given in unary (using scaling, a psuedo-approximation algorithm is also presented for the case of binary vertex weights). This problem is of considerable practical significance, especially in VLSI design.>

The strong link between matroids and matching is used to extend the ideas that resulted in the design of random NC (RNC) algorithms for matching to obtain RNC algorithms for the matroid union, intersection, and matching problems, and for linearly representable matroids. As a consequence, RNC algorithms for the well-known problems of finding an arborescence and a maximum cardinality set of edge-disjoint spanning trees in a graph are obtained. The key tools used are linear algebra and randomization.

We build on the classical greedy sequential set cover algorithm, in the spirit of the primal-dual schema, to obtain simple parallel approximation algorithms for the set cover problem and its generalizations. Our algorithms use randomization, and our randomized voting lemmas may be of independent interest. Fast parallel approximation algorithms were known before for set cover, though not for any of its generalizations.>

Article Approximate max-flow min-(multi)cut theorems and their applications Share on Authors: Naveen Garg View Profile , Vijay V. Vazirani View Profile , Mihalis Yannakakis View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 698–707https://doi.org/10.1145/167088.167266Online:01 June 1993Publication History 60citation1,484DownloadsMetricsTotal Citations60Total Downloads1,484Last 12 Months30Last 6 weeks2 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

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut.This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem.If k is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal.Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.1

We consider the version of the multicommodity flow problem in which the objective is to maximize the sum of commodities routed. Garg, Vazirani and Yannakakis proved that the minimum multicut and maximum flow ratio for this problem can be bounded by O(log k), where k is the number of commodities. In this note we improve this ratio to O(1) for planar graphs, and more generally to O(r3) for graphs with an excluded Kr, r minor. The proof is based on the network decomposition theorem of Klein, Plotkin and Rao. Our proof is constructive and yields approximation algorithms, with the same factors, for the minimum multicut problem on such networks.

The authors give a parallel algorithm for finding vertex disjoint $s_1 ,t_1 $ and $s_2 ,t_2 $ paths in an undirected graph G. An important step in solving the general problem is solving the planar case. A new structural property yields the parallelization, as well as a simpler linear-time sequential algorithm for this case. The algorithm is extended to the nonplanar case by giving a parallel algorithm for finding a Kuratowski homeomorph, and, in particular, a homeomorph of $K_{3,3} $, in a nonplanar graph. The algorithms are processor efficient; in each case, the processor-time product of the algorithms is within a polylogarithmic factor of the best-known sequential algorithm.

Two simple approximation algorithms are presented for the minimum k-cut problem. Each algorithm finds a k-cut having weight within a factor of (2-2/k) of the optimal. One of the algorithms is particularly efficient, requiring a total of only n-1 maximum flow computations for finding a set of near-optimal k-cuts, one for each value of k between 2 and n.>

Article Free Access Share on An optimal algorithm for on-line bipartite matching Authors: R. M. Karp University of California at Berkeley & International Computer Science Institute University of California at Berkeley & International Computer Science InstituteView Profile , U. V. Vazirani Cornell University Cornell UniversityView Profile , V. V. Vazirani View Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990Pages 352–358https://doi.org/10.1145/100216.100262Published:01 April 1990Publication History 439citation3,555DownloadsMetricsTotal Citations439Total Downloads3,555Last 12 Months519Last 6 weeks66 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

Given a graph G and two pairs of vertices s/sub 1/, t/sub 1/ and s/sub 2/, t/sub 2/, the two disjoint paths problem asks for vertex-disjoint paths connecting s/sub i/ with t/sub i/, i=1, 2. A fast parallel (NC) algorithm is given for this problem, which has applications in certain routing situations. If G is nonplanar, an algorithm that finds a Kuratowski homeomorph in G (i.e. a subgraph homeomorphic to K/sub 3.3/ or K/sub 5/) is given. This complements the known NC planarity algorithms, which give a planar embedding in the positive case; the algorithm provides a certificate of nonplanarity in the negative case. Both algorithms are processor efficient; in each case, the processor-time product is within a polylogarithmic factor of the best known sequential algorithm.>

The following issues in computational complexity remain imprecisely understood: The striking difference in the complexities of computing the permanent and determinant of a matrix despite their similar looking formulae, the complexity of checking if a directed graph contains an even length cycle, and the complexity of computing the number of perfect matchings in a graph using Pfaffian orientations. Via polynomial time equivalences, we show inter-relationships among these issues.

An efficient parallel algorithm $({\text{RNC}}^2 )$ for the two-processor scheduling problem is presented. An interesting feature of this algorithm is that it finds a highest-level-first schedule; such a schedule defines a lexicographically first solution to this problem in a natural way. A key ingredient of the algorithm is a generalization of a theorem of Tutte which establishes a one-to-one correspondence between the bases of the Tutte matrix of a graph and the sets of matched nodes in maximum matchings in the graph.

A new algorithm for finding a maximum matching in a general graph is presented; its special feature being that the only computationally non-trivial step required in its execution is the inversion of a single integer matrix.Since this step can be parallelized, we get a simple parallel (RNC2) algorithm.At the heart of our algorithm lies a probabilistic lemma, the isolating lemma.We show applications of this lemma to parallel computation and randomized reductions.

Random Polynomial Time (Rp) is currently considered to be the class of tractable computational problems. Here one assumes a source of truly random bits. However, the known sources of randomness are imperfect. They can be modeled as an adversary source, called slightly-random source. Slightlyrandom Polynomial Time (SRp) is the class of problems solvable in polynomial time using such a source. SRp is thus a more realistic definition of a tractable computational problem. In this paper we give an affirmative answer to the question "is Rp = SRp?" Our proof method is constructive: given an Rp algorithm for a problem, we show how to obtain an SRp algorithm for it. Studying the relationship between randomized and deterministic computation is currently an important issue. A central question here is "is Rp = P?" Our result may be a step towards answering this question.

For all known NP-complete problems the number of solutions in instances having solutions may vary over an exponentially large range. Furthermore, most of the well-known ones, such as satisfiability, are parsimoniously interreducible, and these can have any number of solutions between zero and an exponentially large number. It is natural to ask whether the inherent intractability of NP-complete problems is caused by this wide variation. In this paper we give a negative answer to this using randomized reductions. We show that the problems of distinguishing between instances of SAT having zero or one solution, or finding solutions to instances of SAT having unique solutions, are as hard as SAT itself. Several corollaries about the difficulty of specific problems follow. For example if the parity of the number of solutions of SAT can be computed in RP then NP = RP. Some further problems can be shown to be hard for NP or DP via randomized reductions.

The two-processor scheduling problem is perhaps the most basic problem in scheduling theory, and several efficient algorithms have been discovered for it. However, these algorithms are inherently sequential in nature. We give a fast parallel (R-NC) algorithm for this problem. Interestingly enough, our algorithm for this purely combinatoric-looking problem draws on some powerful algebraic methods.

Cryptographically secure pseudo-random number generators known so far suffer from the handicap of being inefficient; the most efficient ones can generate only one bit on each modular multiplication (n/sup 2/ steps). Blum, Blum and Shub ask the open problem of outputting even two bits securely. We state a simple condition, the XOR-Condition, and show that any generator satisfying this condition can output logn bits on each multiplication. We also show that the logn least significant bits of RSA, Rabin's Scheme, and the x/sup 2/ mod N generator satisfy boolean predicates of these bits are secure. Furthermore, we strengthen the security of the x/sup 2/ mod N generator, which being a Trapdoor Generator, has several applications, by proving it as hard as Factoring.

We examine the problem of routing wires on a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case "channel-width" needed to route an n × n array, and develop provably good heuristics for the general case. An interesting "rounding algorithm" for obtaining integral approximations to solutions of linear equations is used to show the near-optimality of single-turn routings in the worst-case.

We define the class of trapdoor pseudo-random number generators, and introduce a new technique for using these in cryptography. As an application for this technique, we present a provably secure protocol for One-Bit Disclosures i.e. for giving a one-bit message in exchange for receipt.

We prove a natural encoding scheme intractable (by showing it UR-complete, a technique which may be used when a problem does not yield to a proof of NP-completeness). This is the first non number-theoretic problem that is UR-complete but not known to be NP-complete. We also redefine UR-completeness (henceforth refered to as PR-completeness) in probabilistic terms thus making the notion conceptually simpler. Our result suggests that PR-completeness may be a more widely applicable technique than was previously believed.

In this paper we present an 0(√|V|·|E|) algorithm for finding a maximum matching in general graphs. This algorithm works in 'phases'. In each phase a maximal set of disjoint minimum length augmenting paths is found, and the existing matching is increased along these paths. Our contribution consists in devising a special way of handling blossoms, which enables an O(|E|) implementation of a phase. In each phase, the algorithm grows Breadth First Search trees at all unmatched vertices. When it detects the presence of a blossom, it does not 'shrink' the blossom immediately. Instead, it delays the shrinking in such a way that the first augmenting path found is of minimum length. Furthermore, it achieves the effect of shrinking a blossom by a special labeling procedure which enables it to find an augmenting path through a blossom quickly.