We give a new mathematical formulation of market equilibria in exchange economies using an indirect utility function : the function of prices and income that gives the maximum utility achievable. The formulation is a convex program and can be solved when the indirect utility function is convex in prices. We illustrate that many economies, including: —Homogeneous utilities of degree α ∈ [0, 1] in Fisher economies—this includes Linear, Leontief, Cobb-Douglas — Resource allocation utilities like multi-commodity flows satisfy this condition and can be efficiently solved. Further, we give a natural tâtonnement type price-adjusting algorithm in these economies. Our algorithm, which is applicable to a larger class of utility functions than previously known weak gross substitutes , mimics the natural dynamics for the markets as suggested by Walras: it iteratively adjusts a good’s price upward when the demand for that good under current prices exceeds its supply; and downward when its supply exceeds its demand. The algorithm computes an approximate equilibrium in a number of iterations that is independent of the number of traders and is almost linear in the number of goods.

Recent work has shown that the classical framework of solving optimization problems by obtaining a fractional solution to a linear program (LP) and rounding it to an integer solution can be extended to the online setting using primal-dual techniques. The success of this new framework for online optimization can be gauged from the fact that it has led to progress in several longstanding open questions. However, to the best of our knowledge, this framework has previously been applied to LPs containing only packing or only covering constraints, or minor variants of these. We extend this framework in a fundamental way by demonstrating that it can be used to solve mixed packing and covering LPs online, where packing constraints are given offline and covering constraints are received online. The objective is to minimize the maximum multiplicative factor by which any packing constraint is violated, while satisfying the covering constraints. Our results represent the first algorithm that obtains a polylogarithmic competitive ratio for solving mixed LPs online. We then consider two canonical examples of mixed LPs: unrelated machine scheduling with startup costs, and capacity constrained facility location. We use ideas generated from our result for mixed packing and covering to obtain polylogarithmic-competitive algorithms for these problems. We also give lower bounds to show that the competitive ratios of our algorithms are nearly tight.

Multi-level marketing refers to a marketing approach in which buyers are encouraged to take an active role in promoting the product. This is done by offering them a reward for each successful referral of the product to other prospective buyers. To encourage potential customers to buy early and to give referrals to influential people, these mechanisms also reward indirect referrals --- a direct referral linked to the buyer through other direct referrals. Doing so can make the referral/reward system vulnerable to sybil attacks --- where profit maximizers create several replicas in order to maximize their rewards.

We consider a scenario in which a database stores sensitive data of users and an analyst wants to estimate statistics of the data. The users may suffer a cost when their data are used in which case they should be compensated. The analyst wishes to get an accurate estimate, while the users want to maximize their utility. We want to design a mechanism that can estimate statistics accurately without compromising users' privacy.

Let G=(V,E) be a supply graph and H=(V,F) a demand graph defined on the same set of vertices. An assignment of capacities to the edges of G and demands to the edges of H is said to satisfy the cut condition if for any cut in the graph, the total demand crossing the cut is no more than the total capacity crossing it. The pair (G,H) is called cut-sufficient if for any assignment of capacities and demands that satisfy the cut condition, there is a multiflow routing the demands defined on $H$ within the network with capacities defined on G.

Routing games are used to to understand the impact of individual users’ decisions on network efficiency. Most prior work on routing games uses a simplified model of network flow where all flow exists simultaneously, and users care about either their maximum delay or their total delay. Both of these measures are surrogates for measuring how long it takes to get all of a user's traffic through the network. We attempt a more direct study of how competition affects network efficiency by examining routing games in a flow over time model. We give an efficiently computable Stackelberg strategy for this model and show that the competitive equilibrium under this strategy is no worse than a small constant times the optimal, for two natural measures of optimality.

We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-makespan scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle. The approximation guarantees that most of our algorithms achieve are of the order of $\sqrt{{n}/{\ln n}}$. We show that this is the inherent difficulty of the problems by proving matching lower bounds. We also give an improved lower bound for the problem of approximating a monotone submodular function everywhere. In addition, we present an algorithm for approximating submodular functions with a special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work.

Gupta et al. [J. ACM, 54 (2007), article 11] and Gupta, Kumar, and Roughgarden [in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365–372] recently developed an elegant framework for the development of randomized approximation algorithms for rent-or-buy network design problems. The essential building block of this framework is an approximation algorithm for the underlying network design problem that admits a strict cost sharing scheme. Such cost sharing schemes have also proven to be useful in the development of approximation algorithms in the context of two-stage stochastic optimization with recourse. The main contribution of this paper is to show that the Steiner forest problem admits cost shares that are 3-strict and 4-group-strict. As a consequence, we derive surprisingly simple approximation algorithms for the multicommodity rent-or-buy and the multicast rent-or-buy problems with approximation ratios 5 and 6, improving over the previous best approximation ratios of 6.828 and 12.8, respectively. We also show that no approximation ratio better than 4.67 can be achieved using the sample-and-augment framework in combination with the currently best known Steiner forest approximation algorithms. In the context of two-stage stochastic optimization, our result leads to a 6-approximation algorithm for the stochastic Steiner tree problem in the black-box model and a 5-approximation algorithm for the stochastic Steiner forest problem in the independent decision model.

In routing games with infinitesimal players, it follows from well-known convexity arguments that equilibria exist and are unique (up to induced delays, and under weak assumptions on delay functions). In routing games with players that control large amounts of flow, uniqueness has been demonstrated only in limited cases: in 2-terminal, nearly-parallel graphs; when all players control exactly the same amount of flow; when latency functions are polynomials of degree at most three. In this work, we answer an open question posed by Cominetti, Correa, and Stier-Moses (ICALP 2006) and show that there may be multiple equilibria in atomic player routing games. We demonstrate this multiplicity via two specific examples. In addition, we show our examples are topologically minimal by giving a complete characterization of the class of network topologies for which unique equilibria exist. Our proofs and examples are based on a novel characterization of these topologies in terms of sets of circulations.

We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions.The new problems include submodular load balancing, which generalizes load balancing or minimum-makespan scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle.The approximation guarantees for most of our algorithms are of the order of radic(n/ln n). We show that this is the inherent difficulty of the problems by proving matching lower bounds.We also give an improved lower bound for the problem of approximately learning a monotone submodular function. In addition, we present an algorithm for approximately learning submodular functions with special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work. This demonstrates that if there are significantly stronger lower bounds for this problem, they rely on more general submodular functions.

Why might markets tend toward and remain near equilibrium prices? In an effort to shed light on this question from an algorithmic perspective, this paper formalizes the setting of Ongoing Markets, by contrast with the classic market scenario, which we term One-Time Markets. The Ongoing Market allows trade at non-equilibrium prices, and, as its name suggests, continues over time. As such, it appears to be a more plausible model of actual markets.

We consider storage in an extremely large-scale distributed computer system designed for stream processing applications. In such systems, both incoming data and intermediate results may need to be stored to enable analyses at unknown future times. The quantity of data of potential use would dominate even the largest storage system. Thus, a mechanism is needed to keep the data most likely to be used. One recently introduced approach is to employ retention value functions, which effectively assign each data object a value that changes over time in a prespecified way [Douglis et al.2004]. Storage space for data entering the system is reclaimed automatically by deleting data of the lowest current value. In such large systems, there will naturally be multiple file systems available, each with different properties. Choosing the right file system for a given incoming stream of data presents a challenge. In this article we provide a novel and effective scheme for optimizing the placement of data within a distributed storage subsystem employing retention value functions. The goal is to keep the data of highest overall value, while simultaneously balancing the read load to the file system. The key aspects of such a scheme are quite different from those that arise in traditional file assignment problems. We further motivate this optimization problem and describe a solution, comparing its performance to other reasonable schemes via simulation experiments.

We consider storage in an extremely large-scale distributed computer system designed for stream processing applications. In such systems, incoming data and intermediate results may need to be stored to enable future analyses. The quantity of such data would dominate even the largest storage system. Thus, a mechanism is needed to keep the most useful data. One recently introduced approach is to employ retention value functions, which effectively assign each data object a value that changes over time. Storage space is then reclaimed automatically by deleting data of lowest current value. In such large systems, there can naturally be multiple file systems available, each with different properties. Choosing the right file system for a given incoming data stream presents a challenge. In this paper we provide a novel and effective scheme for optimizing the placement of data within a distributed storage subsystem employing retention value functions. The goal is to keep the data of highest overall value, while simultaneously balancing the read load to the file system.

Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous. Traditionally, flows over time are solved in time‐expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static flows, its main and often fatal drawback is the enormous size of the time‐expanded network. We present several approaches for coping with this difficulty. First, inspired by the work of Ford and Fulkerson on maximal s‐t‐flows over time (or “maximal dynamic s‐t‐flows”), we show that static length‐bounded flows lead to provably good multicommodity flows over time. Second, we investigate “condensed” time‐expanded networks which rely on a rougher discretization of time. We prove that a solution of arbitrary precision can be computed in polynomial time through an appropriate discretization leading to a condensed time‐expanded network of polynomial size. In particular, our approach yields fully polynomial‐time approximation schemes for the NP‐hard quickest min‐cost and multicommodity flow problems. For single commodity problems, we show that storage of flow at intermediate nodes is unnecessary, and our approximation schemes do not use any.

In the multi-commodity rent-or-buy network design problem (MRoB) we are given a network together with a set of k terminal pairs R = (s_1, t_1), ..., (s_k, t_k). The goal is to install capacities on the edges of the network so that a prescribed amount of flow fi can be routed between all terminal pairs si and ti simultaneously. We can either rent capacity on an edge at some cost per unit flow or buy infinite capacity on an edge at some larger fixed cost. The overall objective is to install capacities at a minimum total cost.The version of the stochastic Steiner tree problem (SST) considered here is the Steiner tree problem in the model of two-stage stochastic optimization with recourse. In stage one, there is a known probability distribution on subsets of vertices and we can choose to buy a subset of edges at a given cost. In stage two, a subset of vertices T from the prior known distribution is realized, and additional edges can be bought at a possibly higher cost. The objective is to buy a set of edges in stages one and two so that all vertices in T are connected, and the expected cost is minimized.Gupta et al. (FOCS '03) give a randomized scheme for the MRoB problem that was both used subsequently to improve the approximation ratio for this problem, and extended to yield the best approximation algorithm for SST. One building block of this scheme is a good approximation algorithm for Steiner forests.We present a surprisingly simple 5-approximation algorithm for MRoB and 6-approximation for SST, improving on the best previous guarantees of 6.828 and 12.6, and show that no approximation ratio better than 4.67 can be achieved using the above mentioned randomized scheme in combination with the currently best known Steiner forest approximation algorithms. A key component of our approach are cost shares that are 3-strict for the unmodified primal-dual Steiner forest algorithm.

We prove the existence of tolls to induce multicommodity, heterogeneous network users that independently choose routes minimizing their own linear function of tolls versus latency to collectively form the traffic pattern of a minimum average latency flow. This generalizes both the previous known results of the existence of tolls for multicommodity, homogeneous users (Beckman et al., 1956) and for single commodity, heterogeneous users (Cole et al., 2003). Unlike previous proofs for single commodity users in general graphs, our proof is constructive - it does not rely on a fixed point theorem - and results in a simple polynomial-sized linear program to compute tolls when the number of different types of users is bounded by a polynomial. We show that our proof gives a complete characterization of flows that are enforceable by tolls. In particular, tolls exist to induce any traffic pattern that is the result of minimizing an arbitrary function from R/sup E(G)/ to the reals that is nondecreasing in each of its arguments. Thus, tolls exist to induce flows with minimum average weighted latency, minimum maximum latency, and other natural objectives. We give an exponential bound on tolls that is independent of the number of network users and the number of commodities. We use this to show that multicommodity tolls also exist when users are not from discrete classes, but instead define a general function that trades off latency versus toll preference. Finally, we show that our result extends to very general frameworks. In particular, we show that tolls exist to induce the Nash equilibrium of general nonatomic congestion games to be system optimal. In particular, tolls exist even when 1) latencies depend on user type; 2) latency functions are nonseparable functions of traffic on edges; 3) the latency of a set S is an arbitrary function of the latencies of the resources contained in S. Our exponential bound on size of tolls also holds in this case; and we give an example of a congestion game that shows this is tight; it requires tolls that are exponential in the size of the game.

In the survivable network design problem (SNDP), given an undirected graph and values r/sub ij/ for each pair of vertices i and j, we attempt to find a minimum-cost subgraph such that there are r/sub ij/ disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. K. Jain et al. (1999) propose a version of the problem intermediate in difficulty to these two, called the element connectivity problem (ELC-SNDP, or ELC). These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 (K. Jain, 2001), and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O (log k) approximation algorithm, where k=max/sub i,j/ r/sub ij/. VC-SNDP is not known to have a non-trivial approximation algorithm; however, recently L. Fleischer (2001) has shown how to extend the technique of K. Jain ( 2001) to give a 2-approximation algorithm in the case that r/sub ij//spl isin/{0, 1, 2}. She also shows that the same techniques will not work for VC-SNDP for more general values of r/sub ij/. The authors show that these techniques can be extended to a 2-approximation algorithm for ELC. This gives the first constant approximation algorithm for a general survivable network design problem which allows node failures.

This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lovász, and Schrijver. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the length of the largest absolute function value. The paper also presents a strongly polynomial version in which the number of steps is bounded by a polynomial in the size of the underlying set, independent of the function values.

Abstract A maximum flow over time generalizes standard maximum flow by introducing a time component. The object is to send as much flow from source to sink in T time units as possible, where capacities are interpreted as an upper bound on the rate of flow entering an arc. A related problem is the universally maximum flow, which is to send a flow from source to sink that maximizes the amount of flow arriving at the sink by time t simultaneously for all t ≤ T. We consider a further generalization of this problem that allows arc and node capacities to change over time. In particular, given a network with m arcs and n nodes, arc and node capacities that are piecewise constant functions of time with at most k breakpoints and a time bound T, we show how to compute a flow that maximizes the amount of flow reaching the sink in all time intervals (0, t] simultaneously for all 0 < t ≤ T, in O(k2mn log (kn2/m)) time. The best previous algorithm requires O(nk) maximum‐flow computations on a network with m + n)k arcs and nk nodes. Our algorithm improves on this by a factor of O(nk). © 2001 John Wiley & Sons, Inc.

Very recently, two groups of researchers independently developed the first combinatorial, strongly polynomial-time algorithms for submodular function minimization (Iwata, Fleischer, Fujishige; and Schrijver).In this paper, we improve on these algorithms and show that the ideas generated in the design of these algorithms are helpful in other contexts.This work demonstrates one use of combinatorial algorithms for submodular function minimization.In particular we accomplish three things.First, we improve the complexity of Schrijver's algorithm by designing a push-relabel algorithm for submodular function minimization (SFM).Second, we exploit the common structure shared between submodular function minimization and maximum submodular flow to design the first algorithm for maximum submodular flow that does not depend on an oracle for SFM.The overall time complexity is the same as for SFM.Finally, we design the first algorithms for minimum cost submodular flow that do not depend on an oracle for SFM, using the framework of submodular function minimization of Iwata, Fleischer, Fujishige.We show that optimal dual solutions can be computed in the same time as SFM, and that optimal primal solutions can thus be obtained with one additional maximum submodular flow computation.We give both weakly and strongly polynomial versions.* Part of this work done while on leave at the Fields Institute, Toronto, Canada.

This paper presents the first combinatorial polynomialtime algorithm for minimizing submodular functions, answering an open question posed in 1981 by GrStschel, Love%sz, and Schrijver.The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter.The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the largest length of the function value.The paper also presents a strongly polynomial-time version that runs in time bounded by a polynomial in the size of the underlying set independent of the function value.*A part of this work is done while on leave at the Fields Institute, Toronto, Canada.Partly supported

We describe fully polynomial time approximation schemes for various multicommodity flow problems in graphs with m edges and n vertices. We present the first approximation scheme for maximum multicommodity flow that is independent of the number of commodities k, and our algorithm improves upon the run time of previous algorithms by this factor of k, running in ${{\cal O}^*(\epsilon^{-2}m^2)}$ time. For maximum concurrent flow and minimum cost concurrent flow, we present algorithms that are faster than the current known algorithms when the graph is sparse or the number of commodities k is large, i.e., k > m/n. Our algorithms build on the framework proposed by Garg and Könemann [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1998, pp. 300--309]. They are simple, deterministic, and for the versions without costs, they are strongly polynomial. The approximation guarantees are obtained by comparison with dual feasible solutions found by our algorithm. Our maximum multicommodity flow algorithm extends to an approximation scheme for the maximum weighted multicommodity flow, which is faster than those implied by previous algorithms by a factor of k/log W, where W is the maximum weight of a commodity.

A transshipment problem with demands that exceed network capacity can be solved by sending flow in several waves. How can this be done in the minimum number, T, of waves, and at minimum cost, if costs are piecewise linear convex functions of the flow? In this paper, we show that this problem can be solved using $\min\{ m,\log T,\ub{\Gamma}{U} \}$ maximum flow computations and one minimum (convex) cost flow computation. Here m is the number of arcs, $\Gamma$ is the maximum supply or demand, and U is the maximum capacity. When there is only one sink, this problem can be solved in the same asymptotic time as one minimum (convex) cost flow computation. This improves upon the previous best algorithm to solve the problem without costs by a factor of k. Our solutions start with a stationary fractional flow and use rounding to transform this into an integral flow. The rounding procedure takes O(n) time.

We describe fully polynomial time approximation schemes for various multicommodity flow problems in graphs with m edges and n vertices. We present the first approximation scheme for maximum multicommodity flow that is independent of the number of commodities k, and our algorithm improves upon the runtime of previous algorithms by this factor of k, running in O*(/spl epsiv//sup -2/ m/sup 2/) time. For maximum concurrent flow, and minimum cost concurrent flow, we present algorithms that are faster than the current known algorithms when the graph is sparse or the number of commodities k is large, i.e. k>m/n. Our algorithms build on the framework proposed by Garg and Konemann (1998). They are simple, deterministic, and for the versions without costs, they are strongly polynomial. Our maximum multicommodity flow algorithm extends to an approximation scheme for the maximum weighted multicommodity flow, which is faster than those implied by previous algorithms by a factor of k/log W where W is the maximum weight of a commodity.

A parallelizable (or malleable) task is one which can be run on an arbitrary number of processors, with a task execution time that depends on the number of processors allotted to it. Consider a system of M independent parallelizable tasks which are to be scheduled without preemption on a parallel computer consisting of P identical processors. For each task, the execution time is a known function of the number of processors allotted to it. The goal is to find (1) for each task i, an allotment of processors β, and (2) overall, a non-preemptive schedule assigning the tasks to the processors which minimizes the average response time of the tasks. Equivalently, we can minimize the flow time which is the sum of the completion times of each of the tasks.