Big Red Bits

Using expanders to prove sum-product inequalities in finite fields

September 23rd, 2009 renatoppl No comments

I am happy to have the first guest post of BigRedBits written by Igor Gorodezky about an elegant and exciting result in combinatorics.

————————-

I’m fortunate enough to be spending this semester in beautiful Los Angeles as a core participant in the 2009 long program on combinatorics at IPAM (an NSF-funded math institute on UCLA’s campus). We’ve recently wrapped up the first part of the program, which consisted of tutorial lectures on various topics in combinatorics. There was an abundance of gorgeous mathematics, and with Renato’s kind permission I’d like to hijack his blog and write about what to me was one of the most memorable lectures.

This was a lecture by Jozsef Solymosi of the University of British Columbia describing some of his recent work on the sum-product problem in finite fields. In particular, he outlined a spectral-graph-theoretic proof of a recent sum-product inequality due to Garaev. Solymosi’s proof is an extremely clever and elegant application of spectral graph theory to a classical problem in combinatorial number theory, and so I thought I’d present it here. Before stating the result and giving Solymosi’s proof, let us begin with a very brief introduction to the sum-product problem.

1. Introduction

Given a finite set of real numbers ${A}$ , define the sum set

$\displaystyle A+A = \{a+b \mid a,b \in A\}$

and the product set

$\displaystyle A \cdot A = \{ab \mid a,b \in A\}.$

Both the sum set and the product set clearly must have cardinality between ${|A|}$ and ${|A|^2}$ . Observe that if ${A}$ is an arithmetic progression then ${|A+A| \approx 2|A|}$ while ${|A \cdot A| \approx |A|^2}$ , while if ${A}$ is a geometric progression then ${|A \cdot A| \approx 2|A|}$ while ${|A + A| \approx |A|^2}$ . Intuition suggests that keeping ${|A+A|}$ small by giving ${A}$ lots of additive structure inevitably blows up ${|A \cdot A|}$ , while keep ${|A \cdot A|}$ small by giving ${A}$ lots of multiplicative structure in turn blows up ${|A+A|}$ . For an arbitrary ${A}$ , one would expect at least one of these sets, if not both, to be fairly large.

Estimating the maximum of ${|A+A|}$ and ${|A \cdot A|}$ is the sum-product problem. It was posed in a paper by Erdos and Szemeredi, who proved the existence of a small constant ${c}$ such that

$\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{1+c} \right)$

for any finite ${A}$ . They conjecture that we actually have

$\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{2-\delta} \right)$

for any ${\delta > 0}$ and sufficiently large ${|A|}$ . In other words, the value of ${c}$ in their bound can be made arbitrarily close to 1.

Much ink has been spilled in attempts to push up the value of ${c}$ . At present, the best sum-product bound is due to Solymosi and gives ${c \approx 3/11}$ . As an aside, I want to mention an extremely simple and elegant probabilistic proof of Elekes that gives ${c=1/4}$ ; it is detailed in Alon and Spencer’s classic text The Probabilistic Method, and is an absolute gem (look in the chapter on crossing numbers of graphs).

2. The finite field variant

Solymosi’s IPAM lecture was not, however, on this original sum-product problem, but rather on its natural finite field analogue: if ${A}$ is a subset of ${\mathbb F_p}$ , the finite field of prime order ${p}$ , what can we say about the maximum of ${|A+A|}$ and ${|A \cdot A|}$ ? Observe that it is important to consider fields whose order is prime and not the power of a prime, for in the latter case we could take ${A}$ to be a subring and end up with the degenerate case ${|A|=|A+A|=|A \cdot A|}$ .

Bourgain, Katz and Tao got the party started in 2004 by proving the following sum-product bound.

Theorem 1 For all ${\epsilon > 0}$ there exists ${\delta > 0}$ such that if ${A \subseteq \mathbb F_p }$ with ${p^{\epsilon} < |A| < p^{1+\epsilon}}$ then

$\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{1+\delta} \right).$

We note that the implied constant also depends on ${\epsilon}$ . The best known bound is the following, due to Garaev (2007).

Theorem 2 If ${A \subseteq \mathbb F_p}$ then

$\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( \min\left\{ |A|^{1/2}p^{1/2},|A|^2p^{-1/2} \right\} \right).$

To illustrate the theorem, observe that if ${|A| \approx p^{2/3}}$ then ${\max\{ |A+A|, |A \cdot A| \} = \Omega( |A|^{5/4})}$ . It is this theorem that Solymosi proves using spectral graph theory (Garaev’s original proof went by way of Fourier analysis and the estimation of exponential sums).

3. Solymosi’s proof

In this section we give Solymosi’s proof of Theorem 2 (we will assume familiarity with basic facts about eigenvalues and eigenvectors of adjacency matrices). Let us first establish some notation. Consider a ${d}$ -regular graph ${G}$ and let the eigenvalues of its adjacency matrix be

$\displaystyle d=\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n.$

As usual, we define

$\displaystyle \lambda(G) = \max\{ \lambda_2,|\lambda_n|\}.$

Recall that if ${G}$ is connected and non-bipartite then ${\lambda(G)}$ is strictly smaller than ${d}$ , and such a graph is an expander if ${d-\lambda(G)}$ is bounded below by some constant.

We will make use of a fundamental result in spectral graph theory: the expander mixing lemma.

Lemma 3 Let ${G}$ be a ${d}$ -regular graph with ${n}$ vertices. For all ${S,T \subseteq V(G)}$ we have

$\displaystyle \left| e(S,T) - \frac{d}{n}|S||T| \right| \leq \lambda(G) \sqrt{|S||T|}$

where ${e(S,T)}$ is the number of edges with one endpoint in ${S}$ and the other in ${T}$ .

The proof of the lemma is straightforward; we omit it because of space considerations, but it can be found in the survey on expanders by Linial, Hoory, and Wigderson.

Now, back to Theorem 2: we have a finite field ${\mathbb F_p}$ and a subset ${A}$ . Solymosi proves the desired lower bound on ${\max\{ |A+A|, |A \cdot A| \}}$ by constructing a sum-product graph ${G_{SP}}$ over ${\mathbb F_p}$ and using its spectral properties to reason about ${|A+A|}$ and ${|A \cdot A|}$ . So without further ado, let’s define ${G_{SP}}$ .

The vertex set of ${G_{SP}}$ is ${\left( \mathbb F_p \setminus \{0\} \right) \times \mathbb F_p}$ , and two vertices ${(a,b),(c,d)}$ have an edge between them if ${ac=b+d}$ . It is easy to see that ${G_{SP}}$ has ${p(p-1)}$ vertices and is ${(p-1)}$ -regular (some edges are loops). We also have the following key fact.

Lemma 4 Consider ${(a,b),(c,d) \in V(G_{SP})}$ . If ${a=c}$ or ${b=d}$ then these two vertices have no common neighbor, otherwise they have precisely one.

Proof: This follows from the fact that the unique solution of the system

$\displaystyle \begin{array}{c} ax=b+y \\ cx=d+y \end{array}$

is given by

$\displaystyle \begin{array}{c} x = (b-d)(a-c)^{-1}\\ 2y = x(a+c)-b-d \end{array}$

which is only defined when ${a \neq c, b \neq d}$ . $\Box$

Lemma 4 can be used to show that ${G_{SP}}$ is in fact a very good expander (those more familiar with the literature on expanders will recognize that moreover, ${G_{SP}}$ is almost a Ramanujan graph).

Lemma 5 ${\lambda(G_{SP}) < \sqrt{3p}}$ .

Proof: Let ${M}$ be the adjacency matrix of ${G_{SP}}$ . Recall that the ${(u,v)}$ -entry of ${M^2}$ is the number of walks from ${u}$ to ${v}$ of length 2. If ${u=v}$ , this number is the degree ${p-1}$ , while if ${u \neq v}$ , with ${u=(a,b)}$ and ${v=(c,d)}$ , Lemma 4 tells us that this number is 1 if ${a\neq c}$ and ${b \neq d}$ and 0 otherwise. It follows that

$\displaystyle M^2 = J+(p-2)I-E \ \ \ \ \ (1)$

where ${J}$ is the all-1 matrix, ${I}$ is the identity matrix, and ${E}$ is the adjacency matrix of the graph ${G_E}$ whose vertex set is the same as ${G_{SP}}$ , and in which two vertices ${(a,b)}$ and ${(c,d)}$ are connected by an edge if ${a=c}$ or ${b=d}$ . It is easy to see that ${G_E}$ is a ${(2p-3)}$ -regular graph.

Since ${G_{SP}}$ is regular and its adjacency matrix ${M}$ is symmetric, we know that the all-1 vector is an eigenvector of ${M}$ and all other eigenvectors are orthogonal to it. It is easy to check that ${G_{SP}}$ is connected and not bipartite, so that the eigenvalue ${p-1}$ has multiplicity 1, and for any other eigenvalue ${\theta}$ we have ${|\theta| < p-1}$ .

Given such an eigenvalue ${\theta}$ , let ${\bf v}$ be a corresponding eigenvector. Then by equation~(1),

$\displaystyle \theta^2 \mathbf{v} = (p-2)\mathbf{v} - E \mathbf v$

since ${J\mathbf v}$ is the all-0 vector. Therefore ${p-2-\theta^2}$ is an eigenvalue of ${E}$ .

Now, the degree of ${G_E}$ is an upper bound on the absolute value of every eigenvalue of ${E}$ . It follows that

$\displaystyle p-2-\theta^2 \geq -2p+3$

which implies ${|\theta| < \sqrt{3p}}$ , as desired. $\Box$

So ${G_{SP}}$ is an expander; very good, but what about ${A}$ ? Solymosi introduces ${A}$ into the proof through very clever use of the expander mixing lemma: if we define ${S,T \subseteq V(G_{SP})}$ by

$\displaystyle S=(A \cdot A) \times (-A), \ \quad T=(A^{-1}) \times (A+A)$

then that lemma tells us that

$\displaystyle e(S,T) \leq \frac{|S||T|}{p} + \lambda(G_{SP}) \sqrt{|S||T|} < \frac{|A\cdot A||A+A||A|^2}{p} + \sqrt{3p|A \cdot A||A+A||A|^2}$

where the second inequality used Lemma 5.

But for every ${a,b,c \in A}$ there is an edge between ${(ab,-c) \in S}$ and ${(b^{-1},a+c) \in T}$ , so that ${e(S,T) \geq |A|^3}$ . Using this observation and rearranging the resulting inequality gives

$\displaystyle \sqrt{|A \cdot A||A+A|} > \left( \frac{\sqrt{|A \cdot A||A+A|}}{p|A|}+\sqrt{3}\frac{p^{1/2}}{|A|^2} \right)^{-1}.$

Now, since ${(x+y)^{-1} \geq \frac{1}{2}\min\{x^{-1},y^{-1}\}}$ for positive ${x}$ and ${y}$ , we find that

$\displaystyle \sqrt{|A \cdot A||A+A|} = \Omega\left( \min\left\{ \frac{p|A|}{\sqrt{|A \cdot A||A+A|}}, |A|^2 p^{-1/2} \right\} \right)$

which in turn implies

$\displaystyle \sqrt{|A \cdot A||A+A|} = \Omega\left( \min\left\{ |A|^{1/2}p^{1/2}, |A|^2 p^{-1/2} \right\} \right).$

To finish the proof, we need only cite the two-term AM-GM inequality:

$\displaystyle \max\{ |A+A|, |A \cdot A| \} \geq \frac{|A \cdot A|+|A+A|}{2} \geq \sqrt{|A \cdot A||A+A|} .$

4. A very terse bibliography

Solymosi’s proof is from his paper “Incidences and the spectra of graphs” (requires institutional access).

A more knowledgeable treatment of sum-product problems than I could ever provide can be found in these two entries from Terry Tao’s blog. In these, Tao provides a detailed introduction to the problem, gives the probabilistic proof of Elekes’ bound, discusses an interesting cryptographic application, and provides many references.

Igor Gorodezky

Categories: theory Tags: combinatorics, expanders, finite fields, sum-product, theory

Competitive Auctions

September 17th, 2009 renatoppl No comments

This week I will present the Theory Discussion Group about Competitive Auctions. It is mainly a serie of results in papers from Jason Hartline, Andrew Goldberg, Anna Karlin, Amos Fiat, … The first paper is Competitive Auctions and Digital Goods and the second is Competitive Generalized Auctions. My objective is to begin with a short introduction about Mechanism Design, the concept of truthfulness and the characterization of Truthful Mechanisms for Single Parameter Agents. Then we describe the Random Sampling Auction for Digital Goods and in the end we discuss open questions. I thought writting a blog post was a good way of organizing my ideas to the talk.

1. Mechanism Design and Truthfulness

A mechanism is an algorithm augmented with economic incentives. They are usually applied in the following context: there is an algorithmic problem and the input is distributed among several agents that have some interest in the final outcome and therefore they may try manipulate the algorithm. Today we restrict our attention to a specific class of mechanisms called single parameter agents. In that setting, there is a set ${N}$ consisting of ${n}$ agents and a service. Each agent ${i \in N}$ has a value ${v_i}$ for receiving the service and ${0}$ otherwise. We can think of ${v_i}$ as the maximum player ${i}$ is willing to pay for that service. We call an environment ${\mathcal{X} \subseteq 2^N}$ the subsets of the bidders that can be simultaneously served. For example:

Single item auction: ${\mathcal{X} =\{S; \vert S \vert \leq 1\}}$
Multi item auction: ${\mathcal{X} =\{S; \vert S \vert \leq k\}}$
Digital goods auction: ${\mathcal{X} =2^N}$
Matroid auctions: ${\mathcal{X}}$ is a matroid on ${N}$
Path auctions: ${N}$ is the set of edges in a graph and ${\mathcal{X}}$ is the set of ${s-t}$ -paths in the graph
Knapsack auctions: there is a size ${s_i}$ for each ${i \in N}$ and ${S \in \mathcal{X}}$ iff ${\sum_{i \in S} s_i \leq C}$ for a fixed ${C}$

Most mechanism design problems focus in maximizing (or approximating) the social welfare, i.e., finding ${S \in \mathcal{X}}$ maximizing ${\sum_{i \in S} v_i}$ . Our focus here will be maximizing the revenue of the auctioneer. Before we start searching for such a mechanism, we should first see which properties it is supposed to have, and maybe even first that that, define what we mean by a mechanism. In the first moment, the agents report their valuations ${v_i}$ (which can be their true valuations or lies), then the mechanism decides on an allocation ${S \subseteq N}$ (in a possibly randomized way) and charges a payment ${P_i}$ for each allocated agents. The profit of the auctioneer is ${\sum_{i \in S} P_i}$ and the utility of a bidder is:

$\displaystyle u_i = \left\{ \begin{aligned} v_i - P_i &, i \in S \\ 0 &, i \notin S \end{aligned} \right.$

The agents will report valuations so to maximize their final utility. We could either consider a general mechanism e calculate the profit/social welfare in the game induced by this mechanism or we could design an algorithm that gives incentives for the bidders to report their true valuation. The revelation principle says there is no loss of generality to consider only mechanisms of the second type. The intuition is: the mechanisms of the first type can be simulated by mechanisms of the second type. So, we restrict our attention to mechanisms of the second type, which we call truthful mechanisms. This definnition is clear for deterministic mechanisms but not so clear for randomized mechanisms. There are two such definitions:

Universal Truthful mechanisms: distribution over deterministic truthful mechanisms, i.e., some coins are tossed and based on those coins, we choose a deterministic mechanism and run it. Even if the players knew the random coins, the mechanism would still be truthful.
Truthful in Expectation mechanisms: Let ${u_i(b_i)}$ be the utility of agent ${i}$ if he bids ${b_i}$ . Since it is a randomized mechanism, then it is random variable. Truthful in expectation means that ${\mathop{\mathbb E}[u_i(v_i)] \geq \mathop{\mathbb E}[u_i(b_i)], \forall b_i}$ .

Clearly all Universal Truthful mechanisms are Truthful in Expectation but the converse is not true. Now, before we proceed, we will redefine a mechanism in a more formal way so that it will be easier to reason about:

Definition 1 A mechanism ${\mathcal{M}}$ is a function that associated for each ${v \in {\mathbb R}^N}$ a distribution over elements of ${\mathcal{X}}$ .

Theorem 2 Let ${x_i(v) = \sum_{i \in S \in \mathcal{X}} Pr_{\mathcal{M}(v)}[S]}$ be the probability that ${i}$ is allocated by the mechanism given ${v}$ is reported. The mechanism is truthful iff ${x_i(v)}$ is monotone and each allocated bidder is charged payment:

$\displaystyle P_i = v_i - \frac{1}{x_i(v_i, v_{-i})} \int_0^{v_i} x_i(w, v_{-i}) dw$

This is a classical theorem by Myerson about the characterization of truthful auctions. It is not hard to see that the auction define above is truthful. We just need to check that ${x_i(v_i, v_{-i}) (v_i - P(v_i, v_{-i})) \geq x_i(v'_i, v_{-i}) (v_i - P(v'_i, v_{-i}))}$ for all ${v'_i}$ . The opposite is trickier but is also not hard to see.

Note that this characterization implies the following characterization of deterministic truthful auctions, i.e., auctions that map each ${v \in {\mathbb R}^N}$ to a set ${S \in \mathcal{X}}$ , i.e., the probability distribution is concentrated in one set.

Theorem 3 A mechanism is a truthful deterministic auction iff there is a functions ${f_i(b_{-i})}$ such that for each we allocate to bidder ${i}$ iff ${b_i \geq f_i(b_{-i})}$ and in case it is allocated, we charge payment ${f_i(b_{-i})}$ .

It is actually easy to generate this function. Given a mechanism, ${b_i \mapsto x_i(b_i, b_{-i})}$ is a monotone and is a ${\{0,1\}}$ -function. Let ${f_i(b_{-i})}$ the point where it transitions from ${0}$ to ${1}$ . Now, we can give a similar characterization for Universal Truthful Mechanism:

Theorem 4 A mechanism is a universal truthful randomized auction if there are functions ${f_i(r,b_{-i})}$ such that for each we allocate to bidder ${i}$ iff ${b_i \geq f_i(r,b_{-i})}$ and in case it is allocated, we charge payment ${f_i(r,b_{-i})}$ , where ${r}$ are random bits.

2. Profit benchmarks

Let’s consider a Digital Goods auction, where ${\mathcal{X} = 2^N}$ . Two natural goals for profit extraction would be ${\mathcal{T}(v) = \sum_i v_i}$ and ${\mathcal{F}(v) = \max_i i v_i}$ where we can think of ${v_1 \geq v_2 \geq \hdots \geq v_n}$ , the first is the best profit you can extract charging different prices and the second is the best profit you can hope to extract by charging a fixed price. Unfortunately it is impossible to design a mechanism that even ${O(1)}$ -approximates both benchmarks on every input. The intuition is that ${v_1}$ can be much larger then the rest, so there is no way of setting ${f_1(b_{-1})}$ in a proper way. Under the assumption that the first value is not much larger than the second, we can do a good profit approximation, though. This motivates us to find an universal truthful mechanism that approximates the following profit benchmark:

$\displaystyle \mathcal{F}^{(2)}(v) = \max_{i \geq 2} i v_i$

which is the highest single-price profit we can get selling to at least ${2}$ agents. We will show a truthful mechanism that ${4}$ -approximates this benchmark.

3. Profit Extractors

Profit extractor are building blocks of many mechanisms. The goal of a profit extractor is, given a constant target profit ${C}$ , extract that profit from a set of agents if that is possible. In this first moment, let’s see ${C}$ as an exogenous constant. Consider the following mechanism called CostShare ${_C (v)}$ : find the largest ${k}$ s.t. ${k \cdot v_k \geq C}$ . Then allocate to

Lemma 5 CostShare ${_C}$ is a truthful profit-extractor that can extract profit ${C}$ whenever ${\mathcal{F}(v) = \max_i i v_i \geq C}$ .

Proof: It is clear that it can extract profit at most ${C}$ if ${\mathcal{F}(v) \geq C}$ . We just need to prove it is a truthful mechanism and this can be done by checking the characterization of truthful mechanisms. Suppose that under CostShare ${_C (v)}$ exacly ${k}$ bidders are getting the item, then let’s look at a bidder ${i}$ . If bidder ${i}$ is not getting the item, then his value is smaller than ${C/k}$ , otherwise we could incluse all bidders up to ${i}$ and sell for a price ${C/k_1}$ for some ${k_1 > k}$ . It is easy to see that bidder ${i}$ will get the item just if he changes his value ${v_i}$ to some value greater or equal than ${C/k}$ .

On the other hand, it ${i}$ is currently getting the item under ${v}$ , then increasing his value won’t make it change. It is also clear that for any value ${v_i \geq C/k}$ , he will still get the item. For ${v_i < C/k}$ he doesn’t get it. Suppose it got, then at least ${k+1}$ people get the item, because the price they sell it to ${i}$ must be less than ${v_i < C/k}$ . Thefore, increasing ${v_i}$ back to its original value, we could still sell it to ${k+1}$ players, what is a contradiction, since we assumed we were selling to ${k}$ players.

We checked monotonicity and we also need to check the payments, but it is straightforward to check they satisfy the second condition, since ${x_i(v_i) = 1}$ for ${v_i \geq C/k}$ and zero instead. $\Box$

4. Random Sampling Auctions

Now, using that profit extractor as a building block, the main idea is to estimate ${C}$ smaller than ${\mathcal{F}(v)}$ for one subset of the agents and extract that profit from them using a profit extractor. First we partition ${N}$ is two sets ${N'}$ and ${N''}$ tossing a coin for each agent to decide in which set we will place it, then we calculate ${\mathcal{F}' = \mathcal{F}(v_{N'})}$ and ${\mathcal{F}'' = \mathcal{F}(v_{N''})}$ . Now, we run CostShare ${_{\mathcal{F}'} (v'')}$ and CostShare ${_{\mathcal{F}''} (v')}$ . This is called Random Cost Sharing Auction.

Theorem 6 The Random Cost Sharing Auction is a truthful auction whose revenue ${4}$ -approximates the benchmark ${\mathcal{F}^{(2)}(v)}$ .

Proof: Let ${\mathcal{R}}$ be a random variable associated with the revenue of the Sampling Auction mechanism. It is clear that ${\mathcal{R} = \min \{ \mathcal{F}', \mathcal{F}'' \}}$ . Let’s write ${\mathcal{F}^{(2)}(v) = kp}$ meaning that we sell ${k}$ items at price ${p}$ . Let ${k = k' + k''}$ where ${k'}$ and ${k''}$ are the items among those ${k}$ items that went to ${N'}$ and ${N''}$ respectively. Then, clearly ${\mathcal{F}' \geq p k'}$ and ${\mathcal{F}'' \geq p k''}$ , what gives us:

$\displaystyle \frac{\mathcal{R}}{\mathcal{F}^{(2)}} = \frac{\min\{\mathcal{F}', \mathcal{F}''\}}{\mathcal{F}^{(2)}} \geq \frac{\min\{k'p, k''p\}}{kp} = \frac{\min\{k', k''\}}{k}$

and from there, it is a straighforward probability exercise:

$\displaystyle \frac{\mathop{\mathbb E}[{\mathcal{R}}]}{\mathcal{F}^{(2)}} = \mathop{\mathbb E}\left[{ \frac{\min\{k', k''\}}{k} }\right] = \frac{1}{k} \sum_{i=1}^{k-1} \min\{ i, k-i \} \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k}$

since:

$\displaystyle \frac{k}{2} = \sum_{i = 0}^k i \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k} \leq \frac{k}{4} + 2 \sum_{i = 0}^{k/2} i \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k}$

and therefore:

$\displaystyle \frac{\mathop{\mathbb E}[{\mathcal{R}}]}{\mathcal{F}^{(2)}} \geq \frac{1}{4}$ $\Box$

This similar approximations can be extended to more general environments with very little change. For example, for multi-unit auctions, where ${\mathcal{X} = \{ S; \vert S \vert \leq k \}}$ we use the benchmark ${\mathcal{F}^{(2,k)} = \max_{2 \leq i \leq k} i v_i}$ and we can be ${O(1)}$ -competitive against it, by random-sampling, evaluating ${\mathcal{F}^{(1,k)} = \max_{\leq i \leq k} i v_i}$ on both sets and running a profit extractor on both. The profit extractor is a simple generalization of the previous one.

Categories: theory Tags: game theory, mechanism design, profit maximization, theory

Minimum average cost cycle and TSP

September 2nd, 2009 renatoppl No comments

After some time, I did again Code Jam – well, not again, this is the first time I do Code Jam, but there is a while I don’t do Programming Competitions. Back in my undergrad I remember all the fun I had with my ACM-ICPC team solving problems and discussing algorithms problems. Actually, ICPC was what made me interested in Algorithms and Theory of Computing for the first time. I was remembering that not only because Code Jam because I came across a nice problem whose solution I learned in programming competitions, specifically a technique I learned to solve this problem.

Let’s formulate the problem in a more abstract way: Given a graph ${G = (V,E)}$ and two functions: a cost function ${c:E \rightarrow {\mathbb R}_+}$ and a benefit function ${b:E \rightarrow {\mathbb R}_+}$ , we define the cost-benefit of a set of edges as ${\frac{b(S)}{c(S)}}$ . Now, consider those two questions:

Question I: Find the spanning tree of maximum (minimum) cost-benefit.

Question II: Find the cycle of maximum (minimum) cost-benefit.

The solution of those uses binary search. If we can answer the following query: given ${\beta > 0}$ , is there a cycle (spanning tree) of cost-benefit smaller (larger) than ${\beta}$ ? We either state there is no such tree (cycle) or exhibit that. How can we solve this? It is simple: consider the graph ${G}$ with edge weights given by ${b_e - \beta c_e}$ . Then there is a cycle (spanning tree) of cost benefit ${\leq \beta}$ if and only if there is a cycle (spanning tree) in this graph with transformed weights with negative total weight. Finding a cycle with negative weight is easy and can be done, for example, using Bellman Ford’s algorithm. Finding a spanning tree with negative weights can be done using any minimal spanning tree algorithm, as Kruskal, Prim or Boruvka.

Taking ${c(e) = 1}$ for all ${e \in E}$ we can find using binary search, the cycle with smallest average length, i.e., smallest ${b(C) / \vert C \vert}$ where ${\vert C \vert}$ is the number of edges in the cycle.

Asymmetric Travelling Salesman Problem

We can use this trick just described to design an ${O(\log n)}$ -approximation to the asymmetric TSP problem. Consider we have ${n}$ nodes in ${V}$ and a function ${c: V \times V \rightarrow {\mathbb R}_+}$ , not necessarily symmetric, such that the triangular inequality holds, i.e., ${c(i,j) \leq c(i,k) + c(k,j)}$ . A TSP tour is an ordering ${\pi: \{1, \hdots, n\} \rightarrow V}$ and has total cost:

$\displaystyle c(\pi) = \sum_{j=1}^n c(\pi_j, \pi_{j+1})$

where ${\pi_{n+1} = \pi_1}$ . Let OPT be the cost of the optimal tour. It is NP-complete to calculate the optimal, but consider the following approximation algorithm: find the cycle with smallest average cost. Then remove all the nodes in that cycle except one, in the remaining graph find again the cycle of smallest average cost and remove all nodes except one. Continue doing that until there is just one node left. Taking all those cycles together, we have a strongly connected Eulerian graph (in-degrees are equal to out-degrees) for each node). I claim that the total weight of edges ${E'}$ in this Eulerian graph is:

$\displaystyle c(E') \leq 2 \mathcal{H}_n \cdot OPT$

where ${\mathcal{H}_n = \sum_{j=1}^n \frac{1}{j} = O(\log n)}$ is the harmonic number. Now, since we have this graph we can find an Eulerian tour and transform it into a TSP tour shortcutting when necessary (triangle inequality guarantees that shortcutting doesn’t decrease the cost of the tour). So, we just need to prove the claim.

In fact, it is not hard to see that after removing some nodes, the optimal tour is still ${\leq OPT}$ , where ${OPT}$ is the tour of smallest cost for all nodes. To see this, just take the original tour and shortcut it, for example, if the original tour passed through a sequence of nodes ${i_1, \hdots, i_p}$ but nodes ${i_2, \hdots, i_{p-1}}$ then by triangle inequality:

$\displaystyle c(i_1, i_p) \leq \sum_{j=1}^{p-1} c(i_j, i_{j+1})$

so we can just substitute the edges ${(i_1, i_2), \hdots, (i_{p-1}, i_p)}$ by ${(i_1, i_p)}$ . Now, suppose we do ${k}$ iterations and in the beginning of the ${j^{th}}$ iteration there are ${n_j}$ nodes left. So, clearly the average length of the cycle we picked in the algorithm is ${\leq \frac{OPT}{n_j}}$ and therefore, if ${C_1, \hdots C_k}$ are the cycles chosen, we have: