main-content

## Inhaltsverzeichnis

### On Nontrivial Approximation of CSPs

Constraint satisfaction problems, more simply called CSPs are central in computer science, the most famous probably being Satisfiability, SAT, the basic NP-complete problem. In this talk we survey some results about the optimization version of CSPs where we want to satisfy as many constraints as possible.

One very simple approach to a CSP is to give random values to the variables. It turns out that for some CSPs, one example being Max-3Sat, unless P=NP, there is no polynomial time algorithm that can achieve a an approximation ratio that is superior to what is obtained by this trivial strategy. Some other CSPs, Max-Cut being a prime example, do allow very interesting non-trivial approximation algorithms which do give an approximation ratio that is substantially better than that obtained by a random assignment.

These results hint at a general classification problem of determining which CSPs do admit a polynomial time approximation algorithm that beats the random assignment by a constant factor. Positive results giving such algorithms tend to be based on semi-definite programming while the PCP theorem is the central tool for proving negative result.

We describe many of the known results in the area and also discuss some of the open problems.

### Analysis of Algorithms on the Cores of Random Graphs

The

k-core

of a graph is the largest subgraph of minimum degree at least

k

. It can be found by successively deleting all vertices of degree less than

k

.

The threshold of appearance of the

k

-core in a random graph was originally determined by Pittel, Spencer and the speaker. The original derivation used approximation of the vertex deletion process by differential equations. Many other papers have recently given alternative derivations.

A pseudograph model of random graphs introduced by Bollobás and Frieze, and also Chvátal, is useful for simplifying the original derivation. This model is especially useful for analysing algorothms on the

k

-core of a sparse random graphs, when the average degree is roughly constant. It was used recently to rederive the threshold of appearance of the

k

-core (with J. Cain). In addition, the following have recently been obtained concerning either of the random graphs

G

=

G

(

n

,

c

/

n

),

c

> 1, or

G

=

G

(

n

,

m

),

m

=

cn

/2.

(i) Analysis of a fast algorithm for off-line load balancing when each item has a choice of two servers. This enabled us to determine the threshold of appearance of a subgraph with average degree at least 2

k

in the random graph (with P. Sanders and J. Cain),

(ii) Bounds on the mixing time for the giant component of a random graph. We show that with high probability the random graph has a subgraph

H

with “good” expansion properties and such that

G

H

has only “small” components with “not many” such components attached to any vertex of

H

. Amongst other things, this implies that the mixing time of the random walk on

G

is Θ(log

2

n

) (obtained recently and independently by Fountoulakis and Reed). This work is joint with I. Benjamini and G. Kozma. The subgraph is found by successively deleting the undesired vertices from the 2-core of the random graph.

(iii)Lower bounds on longest cycle lengths in the random graph. These depend on the expected average degree

c

and improve the existing results that apply to small

c

>1 (by Ajtai, Komlós and Szemerédi, Fernandez de la Vega, and Suen). The new bounds arise from analysis of random greedy algorithms. Suen’s bounds for induced cycles are also improved using similar random greedy algorithms. This is joint work with J.H. Kim.

In all cases the analysis is by use of differential equations approximating relevant random variables during the course of the algorithm. Typically, this determines the performance of the algorithms accurately, even if the best bounds are not necessarily achieved by these algorithms.

Nick Wormald

### Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs

For a given graph with weighted vertices, the goal of the minimum-weight dominating set problem is to compute a vertex subset of smallest weight such that each vertex of the graph is contained in the subset or has a neighbor in the subset. A unit disk graph is a graph in which each vertex corresponds to a unit disk in the plane and two vertices are adjacent if and only if their disks have a non-empty intersection. We present the first constant-factor approximation algorithm for the minimum-weight dominating set problem in unit disk graphs, a problem motivated by applications in wireless ad-hoc networks. The algorithm is obtained in two steps: First, the problem is reduced to the problem of covering a set of points located in a small square using a minimum-weight set of unit disks. Then, a constant-factor approximation algorithm for the latter problem is obtained using enumeration and dynamic programming techniques exploiting the geometry of unit disks. Furthermore, we also show how to obtain a constant-factor approximation algorithm for the minimum-weight connected dominating set problem in unit disk graphs.

Christoph Ambühl, Thomas Erlebach, Matúš Mihalák, Marc Nunkesser

### Approximating Precedence-Constrained Single Machine Scheduling by Coloring

This paper investigates the relationship between the dimension theory of partial orders and the problem of scheduling precedence-constrained jobs on a single machine to minimize the weighted completion time. Surprisingly, we show that the vertex cover graph associated to the scheduling problem is exactly the graph of incomparable pairs defined in dimension theory. This equivalence gives new insights on the structure of the problem and allows us to benefit from known results in dimension theory. In particular, the vertex cover graph associated to the scheduling problem can be colored efficiently with at most

k

colors whenever the associated poset admits a polynomial time computable

k

-realizer. Based on this approach, we derive new and better approximation algorithms for special classes of precedence constraints, including

convex bipartite

and

semi-orders

, for which we give

$(1+\frac{1}{3})$

-approximation algorithms. Our technique also generalizes to a richer class of posets obtained by lexicographic sum.

Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson

### Minimizing Setup and Beam-On Times in Radiation Therapy

Radiation therapy is one of the commonly used cancer therapies. The radiation treatment poses a tuning problem: it needs to be effective enough to destroy the tumor, but it should maintain the functionality of the organs close to the tumor. Towards this goal the design of a radiation treatment has to be customized for each patient. Part of this design are intensity matrices that define the radiation dosage in a discretization of the beam head. To minimize the treatment time of a patient the beam-on time and the setup time need to be minimized. For a given row of the intensity matrix, the minimum beam-on time is equivalent to the minimum number of binary vectors with the consecutive “1”s property that sum to this row, and the minimum setup time is equivalent to the minimum number of

distinct

vectors in a set of binary vectors with the consecutive “1”s property that sum to this row. We give a simple linear time algorithm to compute the minimum beam-on time. We prove that the minimum setup time problem is APX-hard and give approximation algorithms for it using a duality property. For the general case, we give a

$\frac {24}{13}$

approximation algorithm. For unimodal rows, we give a

$\frac 97$

approximation algorithm. We also consider other variants for which better approximation ratios exist.

Nikhil Bansal, Don Coppersmith, Baruch Schieber

### On the Value of Preemption in Scheduling

It is well known that on-line preemptive scheduling algorithms can achieve efficient performance. A classic example is the Shortest Remaining Processing Time (SRPT) algorithm which is optimal for flow time scheduling, assuming preemption is costless. In real systems, however, preemption has significant overhead. In this paper we suggest a new model where preemption is costly. This introduces new considerations for preemptive scheduling algorithms and inherently calls for new scheduling strategies. We present a simple on-line algorithm and present lower bounds for on-line as well as efficient off-line algorithms which show that our algorithm performs close to optimal.

Yair Bartal, Stefano Leonardi, Gil Shallom, Rene Sitters

### An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs

Given a positive integer

p

and a complete graph with non-negative edge weights that satisfy the triangle inequality, the

remote-clique

problem is to find a subset of

p

vertices having a maximum-weight induced subgraph. A greedy algorithm for the problem has been shown to have an approximation ratio of 4, but this analysis was not shown to be tight. In this paper, we present an algorithm called

d

-

Greedy Augment

that generalizes this greedy algorithm (they are equivalent when

d

= 1). We use the technique of

factor-revealing linear programs

to prove that

d

-

Greedy Augment

, which has a running time of

O

(

pdn

d

), achieves an approximation ratio of (2

p

– 2)/(

p

+

d

– 2). Thus, when

d

= 1,

d

-

Greedy Augment

achieves an approximation ratio of 2 and runs in time

O

(

pn

), making it the fastest known 2-approximation for the remote-clique problem. The usefulness of factor-revealing LPs in the analysis of

d

-

Greedy Augment

suggests possible applicability of this technique to the study of other approximation algorithms.

Benjamin E. Birnbaum, Kenneth J. Goldman

### Tight Results on Minimum Entropy Set Cover

In the minimum entropy set cover problem, one is given a collection of

k

sets which collectively cover an

n

-element ground set. A feasible solution of the problem is a partition of the ground set into parts such that each part is included in some of the

k

given sets. The goal is to find a partition minimizing the (binary) entropy of the corresponding probability distribution, i.e., the one found by dividing each part size by

n

. Halperin and Karp have recently proved that the greedy algorithm always returns a solution whose cost is at most the optimum plus a constant. We improve their result by showing that the greedy algorithm approximates the minimum entropy set cover problem within an additive error of 1 nat = log

2

e

bits ≃ 1.4427 bits. Moreover, inspired by recent work by Feige, Lovász and Tetali on the minimum sum set cover problem, we prove that no polynomial-time algorithm can achieve a better constant, unless P = NP. We also discuss some consequences for the related minimum entropy coloring problem.

Jean Cardinal, Samuel Fiorini, Gwenaël Joret

### A Tight Lower Bound for the Steiner Point Removal Problem on Trees

Gupta (SODA’01) considered the Steiner Point Removal (SPR) problem on trees. Given an edge-weighted tree

T

and a subset

S

of vertices called

terminals

in the tree, find an edge-weighted tree

T

S

on the vertex set

S

such that the distortion of the distances between vertices in

S

is small. His algorithm guarantees that for any finite tree, the distortion incurred is at most 8. Moreover, a family of trees, where the leaves are the terminals, is presented such that the distortion incurred by any algorithm for SPR is at least 4(1 –

o

(1)). In this paper, we close the gap and show that the upper bound 8 is essentially tight. In particular, for complete binary trees in which all edges have unit weight, we show that the distortion incurred by any algorithm for the SPR problem must be at least 8 (1 –

o

(1)).

T. -H. Hubert Chan, Donglin Xia, Goran Konjevod, Andrea Richa

### Single-Source Stochastic Routing

We introduce and study the following model for routing uncertain demands through a network. We are given a capacitated multicommodity flow network with a single source and multiple sinks, and demands that have known values but unknown sizes. We assume that the sizes of demands are governed by independent distributions, and that we know only the means of these distributions and an upper bound on the maximum-possible size. Demands are irrevocably routed one-by-one, and the size of a demand is unveiled only after it is routed.

A

routing policy

is a function that selects an unrouted demand and a path for it, as a function of the residual capacity in the network. Our objective is to maximize the expected value of the demands successfully routed by our routing policy. We distinguish between

safe

routing policies, which never violate capacity constraints, and

unsafe

policies, which can attempt to route a demand on any path with strictly positive residual capacity.

We design safe routing policies that obtain expected value close to that of an optimal unsafe policy in planar graphs. Unlike most previous work on similar stochastic optimization problems, our routing policies are fundamentally adaptive. Our policies iteratively solve a sequence of linear programs to guide the selection of both demands and routes.

Shuchi Chawla, Tim Roughgarden

### An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem

Given an arc-weighted directed graph

G

= (

V

,

A

,ℓ) and a pair of vertices

s

,

t

, we seek to find an

s

-

twalk

of minimum length that visits all the vertices in

V

. If ℓ satisfies the

asymmetric

triangle inequality, the problem is equivalent to that of finding an

s

-

tpath

of minimum length that visits all the vertices. We refer to this problem as ATSPP. When

s

=

t

this is the well known asymmetric traveling salesman tour problem (ATSP). Although an

O

(log

n

) approximation ratio has long been known for ATSP, the best known ratio for ATSPP is

$O(\sqrt{n})$

. In this paper we present a polynomial time algorithm for ATSPP that has approximation ratio of

O

(log

n

). The algorithm generalizes to the problem of finding a minimum length path or cycle that is required to visit a subset of vertices in a given order.

Chandra Chekuri, Martin Pál

### Online Algorithms to Minimize Resource Reallocations and Network Communication

In this paper, we consider two new online optimization problems (each with several variants), present similar online algorithms for both, and show that one reduces to the other. Both problems involve a control trying to minimize the number of changes that need to be made in maintaining a state that satisfies each of many users’ requirements. Our algorithms have the property that the control only needs to be informed of a change in a users needs when the current state no longer satisfies the user. This is particularly important when the application is one of trying to minimize communication between the users and the control.

The Resource Allocation Problem (RAP) is an abstraction of scheduling malleable and evolving jobs on multiprocessor machines. A scheduler has a fixed pool of resources of total size

T

. There are

n

users, and each user

j

has a resource requirement for

r

$_{j,{\it t}}$

resources. The scheduler must allocate resources ℓ

$_{j,{\it t}}$

to user

j

at time

t

such that each allocation satisfies the requirement (

r

$_{j,{\it t}}$

≤ℓ

$_{j,{\it t}}$

) and the combined allocations do not exceed

T

(∑

j

j

,

t

T

). The objective is to minimize the total number of changes to allocated resources (the number of pairs

j

,

t

where ℓ

$_{j,{\it t}}$

≠ℓ

$_{j, {\it t}+1}$

).

We consider online algorithms for RAP whose resource pool is increased to

sT

and obtain an online algorithm which is

O

(log

s

n

)- competitive. Further we show that the increased resource pool is crucial to the performance of the algorithm by proving that there is no online algorithm using

T

resources which is

f

(

n

)-competitive for any

f

(

n

). Note that our upper bounds all have the property that the algorithms only know the list of users whose requirements are currently unsatisfied and never learn the precise requirements of users. We feel this is important for many applications, since users rarely report underutilized resources as readily as they do unmet requirements. On the other hand, our lower bounds apply to online algorithms that have complete knowledge about past requirements.

The Transmission-Minimizing Approximate Value problem is a generalization of one defined in [1], in which low-power sensors monitor real-time events in a distributed wireless network and report their results to a centralized cache. In order to minimize network traffic, the cache is allowed to maintain approximations to the values at the sensors, in the form of intervals containing the values, and to vary the lengths of intervals for the different sensors so that sensors with fluctuating values are measured less precisely than more stable ones. A constraint for the cache is that the sum of the lengths of the intervals must be within some precision parameter

T

. Similar models are described in [2,3]. We adapt the online randomized algorithm for the RAP problem to solve TMAV problem with similar competitive ratio: an algorithm can maintain

sT

precision and be

O

(log

s

n

)-competitive in transmissions against an adversary maintaining precision

T

.

Further we show that solving TMAV is as hard as solving RAP, by reducing RAP to TMAV. This proves similar lower bounds for TMAV as we had for RAP, when

s

is near 1.

Sashka Davis, Jeff Edmonds, Russell Impagliazzo

### Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs

Motivated by applications in batch scheduling of interval jobs, processes in manufacturing systems and distributed computing, we study two related problems. Given is a set of jobs {

J

1

,...,

J

n

}, where

J

j

has the processing time

p

j

, and an undirected intersection graph

G

=({ 1,2,...,

n

},

E

); there is an edge (

i

,

j

) ∈

E

if the pair of jobs

J

i

and

J

j

cannot be processed in the same batch. At any period of time, we can process a

batch

of jobs that forms an independent set in

G

. The batch completes its processing when the last job in the batch completes its execution. The goal is to minimize the sum of job completion times. Our two problems differ in the definition of

completion time

of a job within a given batch. In the first variant, a job completes its execution when its batch is completed, whereas in the second variant, a job completes execution when its own processing is completed.

For the first variant, we show that an adaptation of the greedy set cover algorithm gives a 4-approximation for perfect graphs. For the second variant, we give new or improved approximations for a number of different classes of graphs. The algorithms are of widely different genres (LP, greedy, subgraph covering), yet they curiously share a common feature in their use of

randomized geometric partitioning

.

### Combinatorial Algorithms for Data Migration to Minimize Average Completion Time

The

data migration

problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. It is modeled by a transfer graph, where vertices represent the storage devices, and the edges represent the data transfers required between pairs of devices. Each vertex has a non-negative weight, and each edge has unit processing time. A vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim (

Journal of Algorithms, 55:42-57, 2005

) gave an LP-rounding 3-approximation algorithm. We give a more efficient primal-dual algorithm that achieves the same approximation guarantee, which can be extended to yield a 5.83-approximation for arbitrary processing times. We also study a variant of the open shop scheduling problem. This is a special case of the data migration problem in which the transfer graph is bipartite and the objective is to minimize the completion times of edges. We present a simple algorithm that achieves an approximation ratio of

${\sqrt{2}}$

≈ 1.414, thus improving the 1.796-approximation given by Gandhi

et al.

(

ACM Transaction on Algorithms, 2(1):116-129

, 2006). We show that the analysis of our algorithm is almost tight.

Rajiv Gandhi, Julián Mestre

### LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times

We consider a scheduling problem on unrelated parallel machines with the objective to minimize the makespan. In addition to its machine dependence, the processing time of any job is dependent on the usage of a scarce renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time. The more of the resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied by Shmoys and Tardos. On the basis of an integer linear programming formulation for (a relaxation of) the problem, we adopt a randomized LP rounding technique from Kumar et al. (FOCS 2005) in order to obtain a deterministic, integral LP solution that is close to optimum. We show how this rounding procedure can be used to derive a deterministic 3.75-approximation algorithm for the scheduling problem. This improves upon previous results, namely a deterministic 6.83-approximation, and a randomized 4-approximation. The improvement is due to the better LP rounding and a new scheduling algorithm that can be viewed as a restricted version of the harmonic algorithm for bin packing.

Alexander Grigoriev, Maxim Sviridenko, Marc Uetz

### Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees

We study two related network design problems with two cost functions. In the buy-at-bulk

k

-Steiner tree problem we are given a graph

G

(

V

,

E

) with a set of terminals

T

⊆

V

including a particular vertex

s

called the root, and an integer

k

≤ |

T

|. There are two cost functions on the edges of

G

$b:E\longrightarrow {\mathbb{R}}^+$

and a distance cost

$r:E\longrightarrow {\mathbb{R}}^+$

. The goal is to find a subtree

H

of

G

rooted at

s

with at least

k

terminals so that the cost ∑

$_{e\in{\it H}}$

b

(

e

)+∑

$_{t\in{\it T}-{\it s}}$

dist

(

t

,

s

) is minimize, where

dist

(

t

,

s

) is the distance from

t

to

s

in

H

with respect to the

r

cost. We present an

O

(log

4

n

k

-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light

k

-Steiner trees. In the shallow-light

k

-Steiner tree problem we are given a graph

G

with edge costs

b

(

e

) and distance costs

r

(

e

) over the edges, and an integer

k

. Our goal is to find a minimum cost (under

b

-cost)

k

-Steiner tree such that the diameter under

r

-cost is at most some given bound

D

. We develop an (

O

(log

n

),

O

(log

3

n

))-approximation algorithm for a relaxed version of Shallow-light

k

-Steiner tree where the solution has at least

$\frac{k}{8}$

terminals. Using this we obtain an (

O

(log

2

n

),

O

(log

4

n

))-approximation for the shallow-light

k

-Steiner tree and an

O

(log

4

n

k

-Steiner tree problem.

M. T. Hajiaghayi, G. Kortsarz, M. R. Salavatipour

### Improved Algorithms for Data Migration

Our work is motivated by the need to manage data on a collection of storage devices to handle dynamically changing demand. As demand for data changes, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the

data migration problem

. This problem was shown to be

NP

-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in [Khuller, Kim and Wan: Algorithms for Data Migration with Cloning,

SIAM J. on Computing

, Vol. 33(2):448–461 (2004)]. In this paper we develop an improved approximation algorithm that gives a bound of 6.5+

o

(1) using various new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5. We also consider the full duplex communication model and develop an improved bound of 4 +

o

(1) for this model, with no external disks.

Samir Khuller, Yoo-Ah Kim, Azarakhsh Malekian

### Approximation Algorithms for Graph Homomorphism Problems

We introduce the

maximum graph homomorphism

(MGH) problem: given a graph

G

, and a target graph

H

, find a mapping

ϕ

:

V

G

V

H

that maximizes the number of edges of

G

that are mapped to edges of

H

. This problem encodes various fundamental NP-hard problems including Maxcut and Max-

k

-cut. We also consider the

multiway uncut

problem. We are given a graph

G

and a set of terminals

T

⊆

V

G

. We want to partition

V

G

into |

T

| parts, each containing exactly one terminal, so as to maximize the number of edges in

E

G

having both endpoints in the same part. Multiway uncut can be viewed as a special case of

prelabeled

MGH where one is also given a prelabeling

${\ensuremath{\varphi}}':U\mapsto V_H,\ U{\subseteq} V_G$

, and the output has to be an extension of

ϕ

′.

Both MGH and multiway uncut have a trivial 0.5-approximation algorithm. We present a 0.8535-approximation algorithm for multiway uncut based on a natural linear programming relaxation. This relaxation has an integrality gap of

$\frac{6}{7}\simeq 0.8571$

, showing that our guarantee is almost tight. For maximum graph homomorphism, we show that a

$\bigl({\ensuremath{\frac{1}{2}}}+{\ensuremath{\varepsilon}}_0)$

-approximation algorithm, for any constant

ε

0

> 0, implies an algorithm for distinguishing between certain average-case instances of the

subgraph isomorphism

problem that appear to be hard. Complementing this, we give a

$\bigl({\ensuremath{\frac{1}{2}}}+\Omega(\frac{1}{|H|\log{|H|}})\bigr)$

-approximation algorithm.

Michael Langberg, Yuval Rabani, Chaitanya Swamy

### Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem

In this paper, we will consider a well-studied inventory model, called the

one-warehouse multi-retailer problem

(OWMR) and its special case the

joint replenishment problem

(JRP). As the name suggests, in this model there is one warehouse that orders a particular commodity from a supplier, in order to serve demand at

N

distinct retailers. We consider a discrete finite planning horizon of

T

periods, and are given the demand

d

it

required for each retailer

i

=1,...,

N

in each time period

t

=1,...,

T

. There are two types of costs incurred:

ordering costs

(to model that there are fixed costs incurred each time the warehouse replenishes its supply on hand from the supplier, as well as the analogous cost for each retailer to be stocked from the warehouse) and

holding costs

(to model the fact that maintaining inventory, at both the warehouse and the retail store, incurs a cost). The aim of the model is to provide an optimization framework to balance the fact that ordering too frequently is inefficient for ordering costs, whereas ordering too rarely incurs excessive holding costs.

Retsef Levi, Maxim Sviridenko

### Hardness of Preemptive Finite Capacity Dial-a-Ride

In the

Finite Capacity Dial-a-Ride problem

the input is a metric space, a set of objects {

d

i

}, each specifying a source

s

i

and a destination

t

i

, and an integer

k

—the capacity of the vehicle used for making the deliveries. The goal is to compute a shortest tour for the vehicle in which all objects can be delivered from their sources to their destinations while ensuring that the vehicle carries at most

k

objects at any point in time. In the

preemptive

version an object may be dropped at intermediate locations and picked up later and delivered. Let

N

be the number of nodes in the input graph. Charikar and Raghavachari [FOCS ’98] gave a min {

O

(log

N

),

O

(

k

)}-approximation algorithm for the preemptive version of the problem. In this paper has no min {

O

(log

$^{\rm 1/4-{\it \epsilon}}$

N

),

k

1 − ε

}-approximation algorithm for any

ε

> 0 unless all problems in NP can be solved by randomized algorithms with expected running time

O

(

n

polylog

n

).

Inge Li Gørtz

### Minimum Vehicle Routing with a Common Deadline

In this paper, we study the following vehicle routing problem: given

n

vertices in a metric space, a specified root vertex

r

(the depot), and a length bound

D

, find a minimum cardinality set of

r

-paths that covers all vertices, such that each path has length at most

D

. This problem is

$\mathcal{NP}$

-complete, even when the underlying metric is induced by a weighted star. We present a 4-approximation for this problem on tree metrics. On general metrics, we obtain an

O

(log

D

) approximation algorithm, and also an

$(O(\log \frac{1}{\epsilon}),1+\epsilon)$

bicriteria approximation. All these algorithms have running times that are almost linear in the input size. On instances that have an optimal solution with one

r

-path, we show how to obtain in polynomial time, a solution using at most 14

r

-paths.

We also consider a linear relaxation for this problem that can be solved approximately using techniques of Carr & Vempala [7]. We obtain upper bounds on the integrality gap of this relaxation both in tree metrics and in general.

Viswanath Nagarajan, R. Ravi

### Stochastic Combinatorial Optimization with Controllable Risk Aversion Level

Due to their wide applicability and versatile modeling power, stochastic programming problems have received a lot of attention in many communities. In particular, there has been substantial recent interest in 2–stage stochastic combinatorial optimization problems. Two objectives have been considered in recent work: one sought to minimize the expected cost, and the other sought to minimize the worst–case cost. These two objectives represent two extremes in handling risk — the first trusts the average, and the second is obsessed with the worst case. In this paper, we interpolate between these two extremes by introducing an one–parameter family of functionals. These functionals arise naturally from a change of the underlying probability measure and incorporate an intuitive notion of risk. Although such a family has been used in the mathematical finance [11] and stochastic programming [13] literature before, its use in the context of approximation algorithms seems new. We show that under standard assumptions, our risk–adjusted objective can be efficiently treated by the Sample Average Approximation (SAA) method [9]. In particular, our result generalizes a recent sampling theorem by Charikar et al. [2], and it shows that it is possible to incorporate some degree of robustness even when the underlying probability distribution can only be accessed in a black–box fashion. We also show that when combined with known techniques (e.g. [4,14]), our result yields new approximation algorithms for many 2–stage stochastic combinatorial optimization problems under the risk–adjusted setting.

Anthony Man–Cho So, Jiawei Zhang, Yinyu Ye

### Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems

Given a (directed) graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we consider fundamental directed connectivity network design problems under the power minimization criteria: the

k

-outconnected and the

k

-connected spanning subgraph problems. For

k

= 1 these problems are at least as hard as the Set-Cover problem and thus have an Ω(ln |

V

|) approximation threshold, while for arbitrary

k

a polylogarithmic approximation algorithm is unlikely. We give an

O

(ln |

V

|)-approximation algorithm for any constant

k

. In fact, our results are based on a much more general

O

(ln |

V

|)-approximation algorithm for the problem of finding a min-power edge-cover of an intersecting set-family; a set-family

${\cal F}$

on a groundset

V

is intersecting if

$X \cap Y,X \cup Y \in {\cal F}$

for any intersecting

$X,Y \in {\cal F}$

, and an edge set

I

covers

${\cal F}$

if for every

$X \in {\cal F}$

there is an edge in

I

entering

X

.

Zeev Nutov

### Better Approximations for the Minimum Common Integer Partition Problem

In the

k

-Minimum Common Integer Partition Problem, abbreviated

k

-MCIP, we are given

k

multisets

X

1

, ...,

X

k

of positive integers, and the goal is to find an integer multiset

T

of minimal size for which for each

i

, we can partition each of the integers in

X

i

so that the disjoint union (multiset union) of their partitions equals

T

. This problem has many applications to computational molecular biology, including ortholog assignment and fingerprint assembly.

We prove better approximation ratios for

k

-MCIP by looking at what we call the

redundancy

of

X

1

, ...,

X

k

, which is a quantity capturing the frequency of integers across the different

X

i

. Namely, we show .614

k

-approximability, improving upon the previous best known (

k

– 1/3)-approximability for this problem. A key feature of our algorithm is that it can be implemented in almost

linear time

.

David P. Woodruff

### On Pseudorandom Generators with Linear Stretch in NC0

We consider the question of constructing cryptographic pseudorandom generators (PRGs) in NC

0

, namely ones in which each bit of the output depends on just a constant number of input bits. Previous constructions of such PRGs were limited to stretching a seed of

n

bits to

n

+

o

(

n

) bits. This leaves open the existence of a PRG with a linear (let alone superlinear) stretch in NC

0

. In this work we study this question and obtain the following main results:

1. We show that the existence of a linear-stretch PRG in NC

0

implies non-trivial hardness of approximation results

without relying on PCP machinery

. In particular, that Max 3SAT is hard to approximate to within some constant.

2. We construct a linear-stretch PRG in NC

0

under a specific intractability assumption related to the hardness of decoding “sparsely generated” linear codes. Such an assumption was previously conjectured by Alekhnovich [1].

We note that Alekhnovich directly obtains hardness of approximation results from the latter assumption. Thus, we do not prove hardness of approximation under new

concrete

assumptions. However, our first result is motivated by the hope to prove hardness of approximation under more general or standard cryptographic assumptions, and the second result is independently motivated by cryptographic applications.

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

### A Fast Random Sampling Algorithm for Sparsifying Matrices

We describe a simple random-sampling based procedure for producing sparse matrix approximations. Our procedure and analysis are extremely simple: the analysis uses nothing more than the Chernoff-Hoeffding bounds. Despite the simplicity, the approximation is comparable and sometimes better than previous work.

Our algorithm computes the sparse matrix approximation in a single pass over the data. Further, most of the entries in the output matrix are quantized, and can be succinctly represented by a bit vector, thus leading to much savings in space.

Sanjeev Arora, Elad Hazan, Satyen Kale

### The Effect of Boundary Conditions on Mixing Rates of Markov Chains

Many natural Markov chains undergo a phase transition as a temperature parameter is varied; a chain can be rapidly mixing at high temperature and slowly mixing at low temperature. Moreover, it is believed that even at low temperature, the rate of convergence is strongly dependent on the environment in which the underlying system is placed. It is believed that the boundary conditions of a spin configuration can determine whether a local Markov chain mixes quickly or slowly, but this has only been verified previously for models defined on trees. We demonstrate that the mixing time of Broder’s Markov chain for sampling perfect and near-perfect matchings does have such a dependence on the environment when the underlying graph is the square-octagon lattice. We show the same effect occurs for a related chain on the space of Ising and “near-Ising” configurations on the two-dimensional Cartesian lattice.

Nayantara Bhatnagar, Sam Greenberg, Dana Randall

### Adaptive Sampling and Fast Low-Rank Matrix Approximation

We prove that any real matrix

A

contains a subset of at most 4

k

/

ε

+ 2

k

log(

k

+1) rows whose span “contains” a matrix of rank at most

k

with error only (1+

ε

) times the error of the best rank-

k

approximation of

A

. We complement it with an almost matching lower bound by constructing matrices where the span of any

k

/2

ε

rows does not “contain” a relative (1+

ε

)-approximation of rank

k

. Our existence result leads to an algorithm that finds such rank-

k

approximation in time

$O \left( M \left( \frac{k}{\epsilon} + k^{2} \log k \right) + (m+n) \left( \frac{k^{2}}{\epsilon^{2}} + \frac{k^{3} \log k}{\epsilon} + k^{4} \log^{2} k \right) \right),$

i.e., essentially

O

(

Mk

/

ε

), where

M

is the number of nonzero entries of

A

. The algorithm maintains sparsity, and in the streaming model [12,14,15], it can be implemented using only 2(

k

+1)(log(

k

+1)+1) passes over the input matrix and

$O \left( \min \{ m, n \} (\frac{k}{\epsilon} + k^{2} \log k) \right)$

additional space. Previous algorithms for low-rank approximation use only one or two passes but obtain an additive approximation.

Amit Deshpande, Santosh Vempala

### Robust Local Testability of Tensor Products of LDPC Codes

Given two binary linear codes

R

and

C

, their tensor product

R

C

consists of all matrices with rows in

R

and columns in

C

. We analyze the “robustness” of the following test for this code (suggested by Ben-Sasson and Sudan [6]): Pick a random row (or column) and check if the received word is in

R

(or

C

). Robustness of the test implies that if a matrix

M

is far from

R

C

, then a significant fraction of the rows (or columns) of

M

are far from codewords of

R

(or

C

).

We show that this test

is

robust, provided one of the codes is what we refer to as

smooth

. We show that expander codes and locally-testable codes are smooth. This complements recent examples of P. Valiant [13] and Coppersmith and Rudra [9] of codes whose tensor product is not robustly testable.

Irit Dinur, Madhu Sudan, Avi Wigderson

### Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

Given an

m

×

n

matrix

A

and an integer

k

less than the rank of

A

, the “best” rank

k

approximation to

A

that minimizes the error with respect to the Frobenius norm is

A

k

, which is obtained by projecting

A

on the top

k

left singular vectors of

A

. While

A

k

is routinely used in data analysis, it is difficult to interpret and understand it in terms of the

original data

, namely the columns and rows of

A

. For example, these columns and rows often come from some application domain, whereas the singular vectors are linear combinations of (up to all) the columns or rows of

A

. We address the problem of obtaining low-rank approximations that are directly interpretable in terms of the

original

columns or rows of

A

. Our main results are two polynomial time randomized algorithms that take as input a matrix

A

and return as output a matrix

C

, consisting of a “small” (i.e., a low-degree polynomial in

k

, 1/

ε

, and log(1/

δ

)) number of actual columns of

A

such that

||

A

CC

+

A

||

F

≤(1+

ε

) ||

A

A

k

||

F

with probability at least 1–

δ

. Our algorithms are simple, and they take time of the order of the time needed to compute the top

k

right singular vectors of

A

. In addition, they sample the columns of

A

via the method of “subspace sampling,” so-named since the sampling probabilities depend on the lengths of the rows of the top singular vectors and since they ensure that we capture entirely a certain subspace of interest.

Petros Drineas, Michael W. Mahoney, S. Muthukrishnan

### Dobrushin Conditions and Systematic Scan

We consider Glauber dynamics on finite spin systems. The mixing time of Glauber dynamics can be bounded in terms of the influences of sites on each other. We consider three parameters bounding these influences —

α

, the total influence on a site, as studied by Dobrushin;

α

′, the total influence of a site, as studied by Dobrushin and Shlosman; and

α

′′, the total influence of a site in any given context, which is related to the path-coupling method of Bubley and Dyer. It is known that if any of these parameters is less than 1 then random-update Glauber dynamics (in which a randomly-chosen site is updated at each step) is rapidly mixing. It is also known that the Dobrushin condition

α

<1 implies that systematic-scan Glauber dynamics (in which sites are updated in a deterministic order) is rapidly mixing. This paper studies two related issues, primarily in the context of systematic scan: (1) the relationship between the parameters

α

,

α

′ and

α

′′, and (2) the relationship between proofs of rapid mixing using Dobrushin uniqueness (which typically use analysis techniques) and proofs of rapid mixing using path coupling. We use matrix-balancing to show that the Dobrushin-Shlosman condition

α

′ < 1 implies rapid mixing of systematic scan. An interesting question is whether the rapid mixing results for scan can be extended to the

α

= 1 or

α

′ = 1 case. We give positive results for the rapid mixing of systematic scan for certain

α

= 1 cases. As an application, we show rapid mixing of systematic scan (for any scan order) for heat-bath Glauber dynamics for proper

q

-colourings of a degree-Δ graph

G

when

q

≥2Δ.

Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

### Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems

Experimental results show that certain message passing algorithms, namely,

survey propagation

, are very effective in finding satisfying assignments in random satisfiable 3CNF formulas. In this paper we make a modest step towards providing rigorous analysis that proves the effectiveness of message passing algorithms for random 3SAT. We analyze the performance of

Warning Propagation

, a popular message passing algorithm that is simpler than survey propagation. We show that for 3CNF formulas generated under the planted assignment distribution, running warning propagation in the standard way works when the clause-to-variable ratio is a sufficiently large constant. We are not aware of previous rigorous analysis of message passing algorithms for satisfiability instances, though such analysis was performed for decoding of Low Density Parity Check (LDPC) Codes. We discuss some of the differences between results for the LDPC setting and our results.

Uriel Feige, Elchanan Mossel, Dan Vilenchik

### Robust Mixing

In this paper, we develop a new “robust mixing” framework for reasoning about adversarially modified Markov Chains (AMMC). Let ℙ be the transition matrix of an irreducible Markov Chain with stationary distribution

π

. An adversary announces a sequence of stochastic matrices

$\{{\mathbb{A}}_t\}_{t > 0}$

satisfying

$\pi{\mathbb{A}}_t = \pi$

. An AMMC process involves an application of ℙ followed by

${\mathbb{A}}_t$

at time

t

. The robust mixing time of an irreducible Markov Chain ℙ is the supremum over all adversarial strategies of the mixing time of the corresponding AMMC process. Applications include estimating the mixing times for certain non-Markovian processes and for reversible liftings of Markov Chains.

Non-Markovian card shuffling processes:

The random-to-cyclic transposition process is a

non-Markovian

card shuffling process, which at time

t

, exchanges the card at position

$t {\pmod n}$

with a random card. Mossel, Peres and Sinclair (2004) showed that the mixing time of this process lies between (0.0345+

o

(1))

n

log

n

and

Cn

log

n

+

O

(

n

) (with

C

≈4 ×10

5

). We reduce the constant

C

to 1 by showing that the random-to-top transposition chain (

a Markov Chain

) has robust mixing time ≤

n

log

n

+

O

(

n

) when the adversarial strategies are limited to those which preserve the symmetry of the underlying Markov Chain.

Reversible liftings:

Chen, Lovász and Pak showed that for a reversible ergodic Markov Chain ℙ, any reversible lifting ℚ of ℙ must satisfy

${\mathcal{T}}({\mathbb{P}}) \leq {\mathcal{T}}(\mathbb{Q})\log (1/\pi_*)$

where

π

*

is the minimum stationary probability. Looking at a specific adversarial strategy allows us to show that

${\mathcal{T}}(\mathbb{Q}) \geq r({\mathbb{P}})$

where

r

(ℙ) is the relaxation time of ℙ. This helps identify cases where reversible liftings cannot improve the mixing time by more than a constant factor.

Murali K. Ganapathy

### Approximating Average Parameters of Graphs

Inspired by Feige (

36th STOC

, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle.

We consider two types of queries. The first type is standard neighborhood queries (i.e.,

what is the i

th

neighbor of vertex v

?

), whereas the second type are queries regarding the quantities that we need to find the average of (i.e.,

what is the degree of vertex v

?

and

what is the distance between u

and v

?

, respectively).

Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial.

Oded Goldreich, Dana Ron

### Local Decoding and Testing for Homomorphisms

Locally decodable codes (LDCs) have played a central role in many recent results in theoretical computer science. The role of finite fields, and in particular, low-degree polynomials over finite fields, in the construction of these objects is well studied. However the role of group homomorphisms in the construction of such codes is not as widely studied. Here we initiate a systematic study of local decoding of codes based on group homomorphisms. We give an efficient list decoder for the class of homomorphisms from any abelian group

G

to a fixed abelian group

H

. The running time of this algorithm is bounded by a polynomial in log|

G

| and an agreement parameter, where the degree of the polynomial depends on

H

. Central to this algorithmic result is a combinatorial result bounding the number of homomorphisms that have large agreement with any function from

G

to

H

. Our results give a new generalization of the classical work of Goldreich and Levin, and give new abstractions of the list decoder of Sudan, Trevisan and Vadhan. As a by-product we also derive a simple(r) proof of the local testability (beyond the Blum-Luby-Rubinfeld bounds) of homomorphisms mapping

${\mathbb{Z}}_p^n$

to ℤ

p

, first shown by M. Kiwi.

Elena Grigorescu, Swastik Kopparty, Madhu Sudan

### Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy

We show that for every integer

k

>1, if Σ

k

, the

k

’th level of the polynomial-time hierarchy, is

worst-case

hard for probabilistic polynomial-time algorithms, then there is a language

L

∈Σ

k

such that for every probabilistic polynomial-time algorithm that attempts to decide it, there is a

samplable

distribution over the instances of

L

, on which the algorithm errs with probability at least 1/2–1/

poly

(

n

) (where the probability is over the choice of instances and the randomness of the algorithm). In other words, on this distribution the algorithm essentially does not perform any better than the algorithm that simply decides according to the outcome of an unbiased coin toss.

Dan Gutfreund

### Randomness-Efficient Sampling Within NC 1

We construct a randomness-efficient

averaging sampler

that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform

AC

0

[⊕]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within

NC

1

. For example, we obtain the following results:

Randomness-efficient error-reduction for uniform probabilistic

NC

1

,

TC

0

,

AC

0

[⊕] and

AC

0

: Any function computable by uniform probabilistic circuits with error 1/3 using

r

random bits is computable by uniform probabilistic circuits with error

δ

using

r

+

O

(log(1/

δ

)) random bits.

Optimal explicit

ε

-biased generator in

AC

0

[⊕]: There is a 1/2

Ω(

n

)

-biased generator

$G:{0, 1}^{O(n)} \to {0, 1}^{2^n}$

for which poly(

n

)-size uniform

AC

0

[⊕] circuits can compute

G

(

s

)

i

given (

s

,

i

) ∈0, 1

O

(

n

)

×0, 1

n

. This resolves a question raised by Gutfreund & Viola (

Random 2004

).

uniform BP ·

AC

0

⊆ uniform

AC

0

/

O

(

n

).

Our sampler is based on the

zig-zag graph product

of Reingold, Vadhan and Wigderson (

Annals of Math 2002

) and as part of our analysis we give an elementary proof of a generalization of Gillman’s

Chernoff Bound for Expander Walks

(

FOCS 1994

).

Alexander Healy

### Monotone Circuits for the Majority Function

We present a simple randomized construction of size

O

(

n

3

) and depth 5.3log

n

+

O

(1) monotone circuits for the majority function on

n

variables. This result can be viewed as a reduction in the size and a partial derandomization of Valiant’s construction of an

O

(

n

5.3

) monotone formula, [15]. On the other hand, compared with the deterministic monotone circuit obtained from the sorting network of Ajtai, Komlós, and Szemerédi [1], our circuit is much simpler and has depth

O

(log

n

) with a small constant. The techniques used in our construction incorporate fairly recent results showing that expansion yields performance guarantee for the belief propagation message passing algorithms for decoding low-density parity-check (LDPC) codes, [3]. As part of the construction, we obtain optimal-depth linear-size monotone circuits for the promise version of the problem, where the number of 1’s in the input is promised to be either less than one third, or greater than two thirds. We also extend these improvements to general threshold functions. At last, we show that the size can be further reduced at the expense of increased depth, and obtain a circuit for the majority of size and depth about

$n^{1+\sqrt{2}}$

and 9.9log

n

.

Shlomo Hoory, Avner Magen, Toniann Pitassi

### Space Complexity vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input

x

, one wants to decide whether

x

satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. Unfortunately, there are nearly no general results connecting standard complexity measures of languages with the hardness of testing them. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity

s

(

n

)≤log

n

there is a language with space complexity

O

(

s

(

n

)) and query complexity 2

$^{\Omega({\it s}({\it n}))}$

. We conjecture that this exponential lower bound is best possible, namely that the query complexity of a languages is at most exponential in its space complexity.

Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space

o

(loglog

n

) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space

O

(log

n

) which are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space

O

(loglog

n

) that is not testable with a constant number of queries, thus showing that the

o

(loglog

n

) bound is best possible. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines which is perhaps the weakest (uniform) computational model that is strictly stronger than finite automata.

Oded Lachish, Ilan Newman, Asaf Shapira

### Consistency of Local Density Matrices Is QMA-Complete

Suppose we have an

n

-qubit system, and we are given a collection of local density matrices

ρ

1

,...,

ρ

m

, where each

ρ

i

describes a subset

C

i

of the qubits. We say that the

ρ

i

are “consistent” if there exists some global state

σ

(on all

n

qubits) that matches each of the

ρ

i

on the subsets

C

i

. This generalizes the classical notion of the consistency of marginal probability distributions.

We show that deciding the consistency of local density matrices is QMA-complete (where QMA is the quantum analogue of NP). This gives an interesting example of a hard problem in QMA. Our proof is somewhat unusual: we give a Turing reduction from Local Hamiltonian, using a convex optimization algorithm by Bertsimas and Vempala, which is based on random sampling. Unlike in the classical case, simple mapping reductions do not seem to work here.

Yi-Kai Liu

### On Bounded Distance Decoding for General Lattices

A central problem in the algorithmic study of lattices is the

closest vector problem

: given a lattice

$\mathcal{L}$

represented by some basis, and a target point

$\vec{y}$

, find the lattice point closest to

$\vec{y}$

.

Bounded Distance Decoding

is a variant of this problem in which the target is guaranteed to be close to the lattice, relative to the minimum distance

$\lambda_1(\mathcal{L})$

of the lattice. Specifically, in the

α

-Bounded Distance Decoding problem (

α

-

BDD

), we are given a lattice

$\mathcal{L}$

and a vector

$\vec{y}$

(within distance

$\alpha\cdot\lambda_1(\mathcal{L})$

from the lattice), and we are asked to find a lattice point

$\vec{x}\in \mathcal{L}$

within distance

$\alpha\cdot\lambda_1(\mathcal{L})$

from the target. In coding theory, the lattice points correspond to codewords, and the target points correspond to lattice points being perturbed by noise vectors. Since in coding theory the lattice is usually fixed, we may “pre-process” it before receiving any targets, to make the subsequent decoding faster. This leads us to consider

α

-

BDD

with pre-processing. We show how a recent technique of Aharonov and Regev [2] can be used to solve

α

-

BDD

with pre-processing in polynomial time for

$\alpha=O\left(\sqrt{(\log{n})/n}\right)$

. This improves upon the previously best known algorithm due to Klein [13] which solved the problem for

$\alpha=O\left(1/n\right)$

. We also establish hardness results for

α

-

BDD

and

α

-

BDD

with pre-processing, as well as generalize our results to other ℓ

p

norms.

Yi-Kai Liu, Vadim Lyubashevsky, Daniele Micciancio

### Threshold Functions for Asymmetric Ramsey Properties Involving Cliques

Consider the following problem: For given graphs

G

and

F

1

,...,

F

k

, find a coloring of the edges of

G

with

k

colors such that

G

does not contain

F

i

in color

i

. For example, if every

F

i

is the path

P

3

on 3 vertices, then we are looking for a proper

k

-edge-coloring of

G

, i.e., a coloring of the edges of

G

with no pair of edges of the same color incident to the same vertex.

Rödl and Ruciński studied this problem for the random graph

G

$_{n,{\it p}}$

in the symmetric case when

k

is fixed and

F

1

=...=

F

k

=

F

. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that

p

bn

− β

for some constants

b

=

b

(

F

,

k

) and

β

=

β

(

F

). Their proof was, however, non-constructive. This result is essentially best possible because for

p

Bn

− β

, where

B

=

B

(

F

,

k

) is a large constant, such an edge-coloring does not exist. For this reason we refer to

n

− β

as a

threshold function

.

In this paper we address the case when

F

1

,...,

F

k

are cliques of different sizes and propose an algorithm that a.a.s. finds a valid

k

-edge-coloring of

G

n

,

p

with

p

bn

− β

for some constants

b

=

b

(

F

1

,...,

F

k

,

k

) and

β

=

β

(

F

1

,...,

F

k

). Kohayakawa and Kreuter conjectured that

$n^{-\beta(F_1,\dots, F_k)}$

is a threshold function in this case. This algorithm can be also adjusted to produce a valid

k

-coloring in the symmetric case.

Martin Marciniszyn, Jozef Skokan, Reto Spöhel, Angelika Steger

### Distance Approximation in Bounded-Degree and General Sparse Graphs

We address the problem of approximating the distance of bounded degree and general sparse graphs from having some predetermined graph property

$\cal{P}$

. Namely, we are interested in sublinear algorithms for estimating the fraction of edges that should be added to / removed from a graph so that it obtains

$\cal{P}$

. This fraction is taken with respect to a given upper bound

m

on the number of edges. In particular, for graphs with degree bound

d

over

n

vertices,

m

=

dn

. To perform such an approximation the algorithm may ask for the degree of any vertex of its choice, and may ask for the neighbors of any vertex.

The problem of estimating the distance to having a property was first explicitly addressed by Parnas et. al. (

ECCC 2004

). In the context of graphs this problem was studied by Fischer and Newman (

FOCS 2005

) in the dense-graphs model. In this model the fraction of edge modifications is taken with respect to

n

2

, and the algorithm may ask for the existence of an edge between any pair of vertices of its choice. Fischer and Newman showed that every graph property that has a testing algorithm in this model with query complexity that is independent of the size of the graph, also has a distance-approximation algorithm with query complexity that is independent of the size of the graph.

In this work we focus on bounded-degree and general sparse graphs, and give algorithms for all properties that were shown to have efficient testing algorithms by Goldreich and Ron (

Algorithmica, 2002

). Specifically, these properties are

k

-edge connectivity, subgraph-freeness (for constant size subgraphs), being a Eulerian graph, and cycle-freeness. A variant of our subgraph-freeness algorithm approximates the size of a minimum vertex cover of a graph in sublinear time. This approximation improves on a recent result of Parnas and Ron (

ECCC 2005

).

Sharon Marko, Dana Ron

### Fractional Matching Via Balls-and-Bins

We relate the problem of finding structures related to perfect matchings in bipartite graphs to a stochastic process similar to throwing balls into bins. We view each node on the left of a bipartite graph as having balls that it can throw into nodes on the right (bins) to which it is adjacent. We show that several simple algorithms based on throwing balls into bins deliver a near-perfect fractional matching, where a perfect fractional matching is a weighted subgraph on all nodes with nonnegative weights on edges so that the total weight incident at each node is 1.

Rajeev Motwani, Rina Panigrahy, Ying Xu

### A Randomized Solver for Linear Systems with Exponential Convergence

The Kaczmarz method for solving linear systems of equations

Ax

=

b

is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose

rate does not depend on the number of equations

in the system. The solver does not even need to know the whole system, but only its small random part. It thus outperforms all previously known methods on extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm.

Thomas Strohmer, Roman Vershynin

### Maintaining External Memory Efficient Hash Tables

In typical applications of hashing algorithms the amount of data to be stored is often too large to fit into internal memory. In this case it is desirable to find the data with as few as possible non-consecutive or at least non-oblivious probes into external memory. Extending a static scheme of Pagh [11] we obtain new randomized algorithms for maintaining hash tables, where a hash function can be evaluated in constant time and by probing only one external memory cell or

O

(1) consecutive external memory cells. We describe a dynamic version of Pagh’s hashing scheme achieving 100% table utilization but requiring (2+

ε

)

n

log

n

space for the hash function encoding as well as (3+

ε

)

n

log

n

space for the auxiliary data structure. Update operations are possible in expected constant amortized time. Then we show how to reduce the space for the hash function encoding and the auxiliary data structure to

O

(

n

loglog

n

). We achieve 100% utilization in the static version (and thus a minimal perfect hash function) and 1–

ε

utilization in the dynamic case.

Philipp Woelfel

### Backmatter

Weitere Informationen