Vizing’s celebrated theorem asserts that any graph of maximum degree Δ admits an edge coloring using at most Δ + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2Δ − 1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with Δ = *O*(log*n*), and they conjectured the existence of online algorithms using Δ(1 + *o*(1)) colors for Δ = *ω*(log*n*). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS’03 and Bahmani et al., SODA’10).

We resolve the above conjecture for *adversarial* vertex arrivals in bipartite graphs, for which we present a (1 + *o*(1))Δ-edge-coloring algorithm for Δ = *ω*(log*n*) known a priori. Surprisingly, if Δ is not known ahead of time, we show that no $\big(\frac{e}{e-1} - \Omega(1) \big) \Delta$-edge-coloring algorithm exists. We then provide an optimal, $\big(\frac{e}{e-1}+o(1)\big)\Delta$-edge-coloring algorithm for unknown Δ = *ω*(log*n*). Key to our results, and of possible independent interest, is a novel fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.

Exploring large-scale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of network exploration is the development of suitable strategies that decide which nodes and edges to probe at each stage of the process.

To model this process, we introduce the *stochastic graph exploration problem*. The input is an undirected graph *G* = (*V*, *E*) with a source vertex *s*, stochastic edge costs drawn from a distribution *π*_{e}, *e* ∈ *E*, and rewards on vertices of maximum value *R*. The goal is to find a set *F* of edges of total cost at most *B* such that the subgraph of *G* induced by *F* is connected, contains *s*, and maximizes the total reward. This problem generalizes the stochastic knapsack problem and other stochastic probing problems recently studied.

Our focus is on the development of efficient nonadaptive strategies that are competitive against the optimal adaptive strategy. A major challenge is the fact that the problem has an Ω(*n*) adaptivity gap even on a tree of *n* vertices. This is in sharp contrast with *O*(1) adaptivity gap of the stochastic knapsack problem, which is a special case of our problem. We circumvent this negative result by showing that *O*(log*n**R*) resource augmentation suffices to obtain *O*(1) approximation on trees and *O*(log*n**R*) approximation on general graphs. To achieve this result, we reduce stochastic graph exploration to a memoryless process—the *minesweeper* problem—which assigns to every edge a probability that the process terminates when the edge is probed. For this problem, interesting in its own, we present an optimal polynomial time algorithm on trees and an *O*(log*n**R*) approximation for general graphs.

We study also the problem in which the maximum cost of an edge is a logarithmic fraction of the budget. We show that under this condition, there exist polynomial-time oblivious strategies that use 1 + *ε* budget, whose adaptivity gaps on trees and general graphs are 1 + *ε* and 8 + *ε*, respectively. Finally, we provide additional results on the structure and the complexity of nonadaptive and adaptive strategies.

*k*-server problem where events are generated by selfish
agents, known as *the selfish k-server problem*. In this setting, there is a set
of

We study randomized algorithms for the online vector bin packing and vector scheduling problems. For
vector bin packing, we achieve a competitive ratio of O(d^{1/B}), where d is the number of
dimensions and B the size of a bin. This improves the previous bound of d^{1/(B-1)}
by a polynomial factor, and is tight up to logarithmic factors. For vector scheduling, we show a lower
bound of W((log d)/(log log d)) on the competitive ratio of randomized
algorithms, which is the first result for randomized algorithms and is asymptotically tight. Finally, we
analyze the widely used ``power of two choices¢ algorithm for vector scheduling,
and show that its competitive ratio is O(log log n + (log d)/(log log d)), which is optimal up to the
additive O(log log n) term that also appears in the scalar version of this algorithm.

In this paper we study the classic online matching problem, introduced in the seminal work of Karp, Vazirani
and Vazirani (STOC 1990), in regular graphs. For such graphs, an optimal deterministic algorithm as well as
efficient algorithms under stochastic input assumptions were known. In this work, we present a novel
randomized algorithm with competitive ratio tending to one on this family of graphs, under adversarial
arrival order. Our main contribution is a novel algorithm which achieves competitive ratio 1-O(sqrt(log d)/
sqrt(d)) in expectation on d-regular graphs. In contrast, we show that all previously-studied online
algorithms have competitive ratio strictly bounded away from one. Moreover, we show the convergence rate of
our algorithm’s competitive ratio to one is nearly tight, as no algorithm achieves competitive ratio better
than 1-O(1/sqrt(d)). Finally, we show that our algorithm yields a similar competitive ratio with high
probability, as well as guaranteeing each vertex a probability of being matched tending to one.

We study the online convex covering problem and online convex packing problem.
The (offline) convex covering problem is modeled by the following convex program:

min_{x Î Rn+ } f(x) s.t. A x ³ 1

where f : R^{n}_{+} ® R_{+} is a monotone and
convex cost function, and A is an m X n matrix with non-negative entries.
Each row of the constraint matrix A corresponds to a covering constraint.
In the online problem, each row of A comes online and the algorithm must maintain a feasible assignment
x and may only increase x over time.
The (offline) convex packing problem is modeled by the following convex program:

max_{y Î Rm+ } å_{j} = 1^{m} y_{j} - g(A^{T} y)

where g : R^{n}_{+} ® R_{+} is a monotone and
convex cost function.
It is the Fenchel dual program of convex covering when g is the convex conjugate of f.
In the online problem, each variable y_{j} arrives online and the algorithm must decide the
value of y_{j} on its arrival.

min

where f : R

max

where g : R

In this paper, we exploit linear programming duality in the online setting, where input arrives on the fly,
from the unique
perspective of designing lower bounds (i.e., hardness results) on the competitive ratio. In particular, we
provide a systematic method (as opposed
to ad hoc case analysis that is typically done)
for obtaining online deterministic and randomized lower bounds on the competitive ratio for a wide
variety of problems. We show the usefulness of our approach by providing new, tight hardness results for
three diverse
online problems: the Vector Bin Packing problem, Ad-auctions (and various
online matching problems), and the Capital Investment problem. Our methods are sufficiently general that
they can
also be used to reconstruct existing lower bounds.
Our approach is in stark contrast to previous works, which exploit linear programming duality to obtain
positive
results, often via the useful primal-dual scheme. We design a general recipe with the opposite aim of
obtaining
negative results via duality. The general idea behind our approach is to construct a parameterized family of
primal linear programs based on a candidate collection of input sequences for proving the lower bound,
where the objective function corresponds to optimizing the competitive ratio.
Solving the parameterized family of primal linear programs optimally would yield a valid lower bound, but is
a challenging
task and limits the tools that can be applied, since analysis must be done precisely and exact optimality
needs to be proved.
To this end, we consider the corresponding parameterized family of dual linear programs and provide feasible
solutions,
where the objective function yields a lower bound on the competitive ratio. This opens up additional doors
for analysis,
including some of the techniques we employ (e.g., continuous analysis, differential equations, etc.), as we
need
not be so careful about exact optimality.
We are confident that our methods can be successfully applied to produce many more lower bounds for a wide
array of online problems.

Online d-dimensional vector packing models many settings such as minimizing
resources in data centers
where jobs have multiple resource requirements (CPU, Memory, etc.). However, no online d-dimensional
vector packing algorithm can achieve a competitive ratio better than d. Fortunately, in many natural
applications, vectors are relatively small, and thus the lower bound does not hold. For sufficiently
small vectors, an O(log d)-competitive algorithm was known. We improve this to a constant competitive ratio,
arbitrarily close to e » 2.718, given that vectors are sufficiently small.
We give improved results for the two dimensional case. For arbitrarily small vectors, the first fit algorithm
for two dimensional vector packing is no better than 2-competitive. We present a natural family of first fit
variants, and for optimized parameters get a competitive ratio » 1.48 for
sufficiently small vectors.
We improve upon the 1.48 competitive ratio -- not via a first fit variant -- and give a competitive
ratio arbitrarily close to 4/3 for packing small, two dimensional vectors. We show that no algorithm
can achieve better than a 4/3 competitive ratio for two dimensional vectors, even if one allows the algorithm
to split vectors among arbitrarily many bins.

We study the following balls and bins stochastic game between a player and an
adversary: there are B bins and a sequence of ball arrival and extraction events. In
an arrival event a ball is stored in an empty bin chosen by the adversary and
discarded if no bin is empty. In an extraction event, an algorithm selects a bin,
clears it, and gains its content.
We are interested in analyzing the gain of an algorithm which serves in the dark without any feedback at
all, i.e., does not see the sequence, the content of the bins, and even the content of the cleared bins
(i.e. an oblivious algorithm). We compare that gain to the gain of an optimal, open eyes, strategy that gets
the same online sequence. We name this gain ratio the "loss of serving in the dark".
The randomized algorithm that was previously analyzed is choosing a bin independently and uniformly at
random, which resulted in a competitive ratio of about 1.69.
We show that although no information is ever provided to the algorithm, using non-uniform probability
distribution reduces the competitive ratio.
Specifically, we design a 1.55-competitive algorithm and establish a lower bound of 1.5. We also prove a
lower bound of 2 against any deterministic algorithm.
This matches the performance of the round robin 2-competitive strategy. Finally, we present an application
relating to a prompt mechanism for bounded capacity auctions.

We consider dynamic pricing schemes in online settings where selfish agents generate
online events. Previous work on online mechanisms has dealt almost entirely with the
goal of maximizing social welfare or revenue in an auction settings. This paper deals
with quite general settings and minimizing social costs. We show that appropriately
computed posted prices allow one to achieve essentially the same performance as the best
online algorithm. This holds in a wide variety of settings. Unlike online algorithms
that learn about the event, and then make enforceable decisions, prices are posted
without knowing the future events or even the current event, and are thus inherently
dominant strategy incentive compatible.
In particular we show that one can give efficient posted price mechanisms for metrical task systems, some
instances of the $k$-server problem, and metrical matching problems. We give both deterministic and
randomized algorithms. Such posted price mechanisms decrease the social cost dramatically over selfish
behavior where no decision incurs a charge. One alluring application of this is reducing the social cost of
free parking exponentially.

In the d-dimensional bin packing problem (VBP), one is given vectors
x_{1},x_{2}, ¼ ,x_{n} Î
**R**^{d} and the goal is to find
a partition into a minimum number of feasible sets: {1,2 ¼ ,n} = È_{i}^{s} B_{i}.
A set B_{i} is feasible if å_{j Î
Bi} x_{j} £ **1**, where
**1** denotes the all 1¢s vector. For online VBP,
it has been
outstanding for almost 20 years
to clarify the gap between the best lower bound W(1) on the competitive ratio
versus the best upper bound of O(d).
We settle this by describing a W(d^{1-e}
) lower bound.
We also give strong lower bounds (of W(d^{(1)/(B)-e}
) ) if the bin size B Î **Z**_{+}
is allowed to grow. Finally, we discuss almost-matching upper bound results for general values of B;
we show an upper bound whose exponent is additively ``shifted by 1" from the lower bound exponent.

Faculty Member

Researcher

Postdoctoral Fellow

University of Pittsburgh

Postdoctoral Fellow

Postdoctoral Fellow

Ph.D. in Computer Science

M.Sc. in Computer Science

B.Sc. in Computer Science