[Lowerbounds, Upperbounds]

Title: Auctions for dynamic environments: WiFi, last-minute tickets and grid computing
Speaker: MohammadTaghi Hajiaghayi,
Affiliation: Carnegie Mellon University

We consider the problem of auction design for dynamic environments, in which agents arrive and depart dynamically and in which goods are inherently temporal. Motivating examples are drawn from the problem of WiFi allocation in coffee houses, last-minute tickets, and scientific grid computing. We provide a characterization for the design of truthful online auctions, such that it is a domnant strategy equilibrium for bidders to reveal their true value for resources immediately upon arrival into a system. The auctions are online, in the sense that they make allocation decisions without knowledge of the future. In a setting without priors, we provide an e-competitive (for efficiency) truthful auction for a limited-supply unit-demand problem, drawing an analogy with the classic secretary problem. We also present a 2-competitive auction (wrt efficiency) for a setting with a reusable resource, and describe a randomized online auction that achieves a competitive ratio for revenue of O(log h), where h is the ratio of maximum value to minimum value among the agents. In closing, we discuss envy-pricing and the concept of “fair equilibrium” versus “dominant equilibrium”and their relation to online auctions, and we end with several interesting directions for future work.

This is from some papers which are joint work with Erik D. Demaine (MIT), Uriel Feige (MSR), David C. Parkes (Harvard), R.D. Kleinberg (Cornell), Mohammad R. Salavatipour (U. Alberta).

Following the suggestion of Mike Dinitz, I have started to investigate Google Calendar. As some of you already know, this blog server exports an ICS file that can be used for many calendar clients. I have just made it easier with a non-https URL:

http://jasmine.aladdin.cs.cmu.edu/Calendar/aladdin.ics

(There is a long story behind why this was in https in the past. Now all you need to know is that this is no longer the case.)

I see that there are still some space quoting issues to be fixed, but at least it is already in a somewhat usable stage. Also, note that Google Calendar seems to update remote calendar once a day or so. Therefore, you don’t see new events that are entered very recently.

I thank Mike for the suggestion. Maybe I will switch to Google Calendar soon. Currently I still use Rainlander on my X40 Tablet but Google Calendar has been growing on me, except that it doesn’t seem to allow me to maintain a TODO list…

Speaker: Jonathan Derryberry

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Lower Bounds for the Binary Search Tree Model

Abstract:

This talk considers the problem of bounding below the cost of accessing a sequence of keys in a binary search tree. We develop a simple lower bound framework for this problem that applies to any binary search tree algorithm, including self-adjusting and offline ones. This new framework can be used to derive two previously known lower bounds.

Title: “The Role of Mathematics in Undergraduate CS & SE Education”

Speaker: Peter B. Henderson, Head
Department of Computer Science and Software Engineering
Butler University

Time and Place: Tuesday May 2, at 12 noon in NSH 3305

Abstract:

Computer science and software engineering are young, maturing disciplines. As with other mathematically based disciplines, such as the natural sciences, economics and engineering, it takes time for the mathematical roots to grow and flourish. The current mathematics requirements for computer science and software engineering majors may not be appropriate, and the mathematics material that is appropriate is not integrated into the courses. Computing Curricula 2001 (CC 2001) and Software Engineering 2004 include discrete mathematics in the core and recommends that this material be covered early. This partly addresses the requirements issue, but not the integration problem. This presentation will identify and motivate the topics to be included in freshman discrete mathematics, discuss curricula issues, present evidence that teaching discrete mathematics and problem-solving early is beneficial, and discuss ways in which mathematical concepts can be integrated and reinforced throughout undergraduate computer science and software engineering curricula.

Bio Sketch:
Ph D, Princeton University, BSEE & MSEE, Clarkson University. Professor Henderson has been actively involved in the effort to ensure computer based mathematics is covered as early as possible in the curriculum and to ensure these concepts are used and built upon in all computer science courses. Over 20 years he developed, evolved and taught Foundations of Computer Science, the first course for all computer science and computer engineering majors at the State University of New York at Stony Brook and Butler University.

In the spring of 1999 Professor Henderson co-founded the math thinking discussion group (www.math-in-cs.org) that is actively trying to promote the importance of mathematics and mathematical thinking in computer science education. He has served on numerous panels at national conferences, run several National Science Foundation sponsored workshops on teaching foundations of computer science, has been a co-principle investigator of 3 National Science Foundation education grants addressing issues relating to teaching mathematics in the context of computer science. In addition, he chaired the Foundations knowledge area for the software engineering curriculum effort.

Name: Michel Goemans
University: MIT
Date: Friday, April 28, 2006
Time: 1:30 to 3:00 pm
Location: Simon Auditorium, Posner Hall
Title of Seminar: Abstract of Bounded-Degree Minimum Spanning Trees

Abstract

In this lecture, we consider a basic problem in network design, namely the minimum cost spanning tree problem with the restriction that all degrees must be at most a given value $k$. This is an NP-hard problem. We show that we can efficiently find a spanning tree of maximum degree at most $k+2$ whose cost is at most the cost of the optimum spanning tree of maximum degree $k$. This is almost best possible. The approach uses a sequence of simple algebraic, polyhedral and combinatorial arguments. It illustrates many techniques and ideas in combinatorial optimization as it involves polyhedral characterizations, uncrossing, matroid intersection, and graph orientations. The result generalizes to the setting where every vertex has both upper and lower bounds. Other extensions will also be discussed.

Name: Andras Prékopa
University: Rutgers Center for Operations Research, University of New Jersey
Date: Friday, April 21, 2006
Time: 1:30 to 3:00 pm
Location: Simon Auditorium
Title of Seminar: On the Relationship Between Probabilistic Constrained Stochastic,
Disjunctive and Miltiobjective Programming

Abstract:

The probabilistic constraint stochastic programming problem can be identified as a special disjunctive programming problem, where, however, the alternative constraints are not given in the same form as the others. The p-efficient points of a multivariate c.d.f. have to be identified and each of them determines an alternative constraint. If the distribution is discrete, then the set of p-efficient points is finite. If it is continuous, then the problem is a semi-infinite disjunctive problem but general theorems ensure the convexity of the set of feasible solutions.

For the discrete case we introduce a multiobjective term into the objective function, by taking the maximum of a finite number of linear functions of a subset of variables, while the entire objective function is to be minimized. Then, if the p-efficient points are known, we convexify the alternative constraints and arrive to a problem such that its dual is of the same type. A duality theorem can be obtained also for the case of a continuous distribution by the use of a limiting procedure or direct reasoning, using nonlinear duality theory.

The numerical solution of problems of this type will be discussed. In both the discrete and continuous distribution cases the duality theorems provide us with the possibility to choose between the primal and dual problems to solve. For the discrete case a cutting plane procedure is available that assumes the knowledge of the p-efficient points. If, however, the components of the random vector in the probabilistic constraint are independent, then a cone generation algorithm creates the p-efficient points and solves the problem simultaneously. For the continuous case a new algorithm is developed, a combination of a cutting plane and a supporting hyperplane algorithms. Its advantage is that in each iteration we obtain lower and upper bounds for the optimum value of the original problem and the difference between the bounds vanishes if we pass to the limit. Below is a list of those papers, that are important sources of information for our theoretical and algorithmic developments.

E. Balas, Disjunctive Programming. Annals of Discrete Math. 5 (1979) 3-51.
E. Balas, Disjunctive programming: Properties of the Convex Hull of Feasible Points.
D. Dentcheva, A. Prékopa, A. Ruszczynski, Concavity and Efficient Points of Discrete
Distributions in Probabilistic Programming. Math. Prog. Ser. A. 89 (2000) 55-77.
L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, K. Makino, Dual-Bounded Generating
Problems: Efficient and Inefficient Points for Discrete Probability Distributions and Sparse
Boxes for Multidimensional Data. Discrete Applied Math. To appear.
É. Komáromi, Duality in Probabilistic Constrained Linear Programming. In: Lecture Notes in
Control and Inf. Sci. 84 (1986) 423-429.
A. Prékopa, B. Vízvári, T. Badics, Programming under Probabilistic Constraint with Discrete
Random Variable. New Trends in Math. Prog. (F. Giovannessi et. al. eds.), Kluwer, 1988. 235-255.
A. Prékopa, Stochastic Programming. Kluwer, 1995.

Copies of the paper will be available at the seminar.

Speaker: Doru-Christian Balcan

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Error Correcting by Linear Programming

Abstract:

The problem of perfectly recovering a signal when only noisy observations are available, lies at the core of signal processing and transmission. Even in relatively simple settings, this task may be hopeless in general, because of the unpredictable nature of the error.

For instance, when the signal is a real-valued, n-dimensional vector $f$, linearly encoded by a known m-by-n matrix $A$ (where m>n), the m-dimensional error vector $e$ may completely obstruct the recovery of $f$ from $Af+e$. If we assume that only a fraction of the observations are corrupted (even if we don’t know which ones, nor how they were altered), suitable conditions on $A$ favor exact decoding, via solving a certain linear program.

In fact, the above problem is naturally related to finding the sparsest solution of a large underdetermined system of linear equations. Known to be NP-hard, this problem has been tackled with greedy approaches but in practice, relaxation techniques were far more successful at finding the sparsest solution (when it exists).

In this talk, I try to follow the approach of Candes, Rudelson, Tao and Vershynin (FOCS’05) at describing this intimate connection between the two problems. Also, I will expose the theoretical guarantees they derived, about when and why the combinatorial problem can be exactly solved via LP (e.g. an answer to the question: how sparse is “sparse enough”? ).

TITLE: Satisfiability and the Giant Component in Online Variants of the Classical Random Models

SPEAKER: David Kravitz

WHEN: April 17, 1:30pm

WHERE: DH 4303

ABSTRACT:

We introduce and study online versions of two classical random structures. The first is a variation on the classical random graph model, the second is the satisfiability model.

We begin with the random graph. Let $c$ be a constant and $(e_1,f_1)$, $(e_2,f_2)$, …, $(e_{cn},f_{cn})$ be a sequence of ordered pairs of edges on vertex set $[n]$ chosen uniformly and independently at random. Let $A$ be an algorithm for the online choice of one edge from each presented pair, and for $i= 1, …, cn$ let $G_A(i)$ be the graph on vertex set $[n]$ consisting of the first $i$ edges chosen by $A$. We prove that all algorithms in a certain class have a critical value $c_A$ for the emergence of a giant component in $G_A( cn )$ (i.e. if $c < c_A$ then with high probability the largest component in $G_A(cn)$ has $o(n)$ vertices and if $c > c_A$ then with high probability there is a component of size $\Omega(n)$ in $G_A(cn)$). We show that a particular algorithm in this class with high probability produces a giant component before $0.385 n$ steps in the process (i.e. we exhibit an algorithm that creates a giant component relatively quickly). The fact that another specific algorithm that is in this class has a critical value resolves a conjecture of Spencer. In addition, we establish a lower bound on the time of emergence of a giant component in any process produced by an online algorithm and show that there is a phase transition for the offline version of the problem of creating a giant component.

Now we consider satisfiability. Given $n$ Boolean variables $x_1,…,x_n$, a $k$-clause is a disjunction of $k$ literals, where a literal is a variable or its negation. Suppose random $k$-clauses are generated one at a time and an online algorithm accepts or rejects each clause as it is generated. Our goal is to accept as many randomly generated $k$-clauses as possible with the condition that it must be possible to satisfy every clause which is accepted. When $cn$ random $k$-clauses on $n$ variables are given, a natural online algorithm known as \emph{Online-Lazy} accepts an expected $(1-\frac{1}{2^k})cn+z_kn$ clauses for some constant $z_k$. If these clauses are given offline, it is possible to do much better, $(1-\frac{1}{2^k})cn+\Omega(\sqrt c)n$ can be accepted \whp. The question of closing the gap between $(1-\frac{1}{2^k})cn+z_kn$ and $(1-\frac{1}{2^k})cn+\Omega(\sqrt c)n$ for the online version was posed by Coppersmith, Gamarnik, Hajiaghayi, and Sorkin. We show that for any $k \geq 1$, any online algorithm will accept less than $(1-\frac{1}{2^k})cn+(\ln 2)n$ $k$-clauses \whp, furthermore we show that this bound is asymptotically tight as $k \to \infty$.

We also introduce a new random model for random $2-SAT$. It is well-known that inn the standard model there is a sharp phase transition, the probability of satisfiability quickly drops as the number of clauses exceeds the number of variables. The location of this phase transition suggests that there is a direct connection between the appearance of a giant in the corresponding $2n$-vertex graph and satisfiability. Here we show that the giant has nothing to do with satisfiability, and in fact the expected degree of a randomly chosen vertex is the important parameter.

Speaker: Chris Wang
Title: Multi-Splay Trees
Date: 2006-04-13, Thursday
Time: 14:00
Place: Wean 7220

In this thesis, we introduce multi-splay trees and prove that multi-splay trees have almost all of the useful properties various specialized binary search trees (BSTs) have. First, we demonstrate a close variant of the splay tree access lemma for multi- splay trees, a lemma that implies multi-splay trees have the O(log n) runtime property, the static finger property, and the static optimality property. Then, we extend the access lemma by showing the remassing lemma, which is similar to the reweighting lemma for splay trees. The remassing lemma shows that multi-splay trees satisfy the working set property and key-independent optimality, and multi-splay trees are competitive to parametrically balanced trees. Furthermore, we also prove that multi-splay trees achieve the O(log log n)-competitiveness and that sequential access in multi-splay trees costs O(n).

Then we naturally extend the static model to allow insertions and deletions and show how to carry out these operations in multi-splay trees to achieve O(log log n)-competitiveness, a result no other BST scheme has been proved to have. In addition, we prove that multi-splay trees satisfy the deque property, which is still an open problem for splay trees since it was conjectured in 1985. While it is easy to construct a BST that satisfies the deque property trivially, no other BST scheme satisfying other useful properties has been proved to have deque property. In summary, these results show that multi-splay trees have most of the important properties satisfied by different binary search trees.

Committee:

Manuel Blum, Carnegie Mellon University
Gary Miller, Carnegie Mellon University
Daniel Sleator, Carnegie Mellon University, chair
Robert Tarjan, Princeton University

Speaker: Maverick Woo
Title: Finger Search on Balanced Search Trees
Date: 2006-04-14, Friday
Time: 15:30
Place: Wean 5409

Committee:

Guy E. Blelloch, Carnegie Mellon University, co-chair
Richard Cole, New York University
Bruce M. Maggs, Carnegie Mellon University, co-chair
Daniel Dominic Kaplan Sleator, Carnegie Mellon University

Abstract:

This thesis introduces the concept of a heterogeneous decomposition of a balanced search tree and apply it to the following problems:

* How can finger search be implemented without changing the representation of a Red-Black Tree, such as introducing extra storage to the nodes?

(Answer: Any degree-balanced search tree can support finger search without modification in its representation by maintaining an auxiliary data structure of logarithmic size and suitably modifying the search algorithm to make use of this auxiliary data structure.)

* Do MultiSplay Trees, which is known to be O(log log n)-competitive to the optimal binary search trees, have the Dynamic Finger property?

(Answer: This is work in progress. We believe the answer is yes.)

WEDNESDAY, April 26, 2006

PROBABILITY IN SCIENCE AND INDUSTRY SEMINAR

4:30 P.M., WeH 7500
Philippe Robert, INRIA, Rocquencourt.

TITLE: Data Structures, Tree Algorithms and Renewal Theorems

ABSTRACT: A tree algorithm is a procedure that divides (splits) recursively into subsets an initial set of n items until each of the subsets obtained has a cardinality strictly less than some fixed number D. These algorithms have a wide range of applications: access protocols in communication networks, divide and conquer algorithms for data structures, leader election in distributed systems, … The asymptotic behavior of additive cost functions associated to these algorithms is presented. When the successive splittings are assumed to be independent then, via an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily without resorting to complex analysis techniques as it is usually the case in this domain. When the successive splittings are not anymore independent but only stationary (dynamical source), it is shown the entropy function of the dynamical system determines the asymptotical behavior of the cost function. The key ingredient of all these results is a generalized renewal theorem.

Joint work with Mohamed.

Refreshments at 4:00 WeH 6220.

Speaker: Varun Gupta

Time: Wednesday 12-1pm

Place: NSH 1507

Title: A gentle introduction to fluid and diffusion limits for queues

Abstract:

To obtain explicit results in queueing theory, it is almost always necessary to make certain strong assumptions about the statistical nature of the process involved. These assumptions are only approximately satisfied in practice, if at all. However, under certain limiting cases one can get results that do hold under weaker conditions. One such condition is when the system is operating close to its maximum capacity or is overloaded. In the latter case, appropriately time and space scaled versions of the stochastic process converge to what are known as fluid and diffusion processes. In my talk, I will informally review the notion of fluid and diffusion limits and illustrate them using examples of non-stationary queues.

Long story short: harddisk crashed, go to download TexPoint again and notice that it’s now shareware, costing 25 dollars, with a Mac version too. See this post for a tiny bit of history.

(Back to harddrive recovery mode.)

TITLE: Chain Programming
SPEAKER: K. Subramani (West Virginia University)
WHEN: April 13, 4:30pm
WHERE: PPB 300

ABSTRACT: Chain Programming is a restricted form of Linear Programming; in a Chain Program, there exists a total ordering on the program variables. In other words, the constraints $x_{1} \le x_{2} \ldots x_{n}$ are either implicitly or explicitly part of the constraint system. At the present juncture, it is not clear whether an arbitrary linear program augmented with a chain is easier to solve than linear programs in general, either asymptotically or computationally. However, if the linear program is constituted entirely of difference constraints, then the total ordering results in an elegant divide and conquer algorithm for the problem of feasibility testing. This approach can be parallelized in straightforward fashion to run on any SIMD or MIMD architecture, thereby greatly enhancing its effectiveness. Inasmuch as difference constraint logic is an integral part of a number of verification problems in both model-checking and real-time scheduling, our result is of particular importance to these communities. One of the surprising consequences of our research is the establishment of a link between Chain Programs over Difference Constraints and a specialized class of Totally Unimoduluar (TUM) matrices called {\em interval} matrices.

Speaker: Mohit Tawarmalani
Date: Friday, April 7, 2006
Time: 1:30 to 3:00 pm
Place: 388 Posner Hall
Title: Convex Extensions and Convexification of Nonlinear Sets

Abstract

We develop a theoretical framework of convex extensions that enables building convex envelopes of many nonlinear functions. We then use the framework to analyze inclusion certificates (that guarantee inclusion of a point in the convex hull of a disjunction) and provide insights into various hierarchies of relaxations. We extend the notion of lifting locally valid inequalities to global validity to generate linear and nonlinear inequalities for continuous nonlinear programming. As a consequence, we develop valid inequalities for certain mixed-integer bilinear sets and a procedure for generating convex hulls for certain disjunctive nonlinear sets.

Speaker: Ryan Williams

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Using Linear Algebra for Faster Solution of NP-hard Problems

Abstract:

We present a connection between two fundamental problems in computer science: the well-known problem of Matrix Multiplication, and the very general problem of 2-CSP (2-Constraint Satisfaction Problem) Optimization which encodes many important graph optimization problems. While Matrix Multiplication is well-known to be a polynomial time problem, 2-CSP Optimization is NP-Hard. Despite the stark computational differences between the two problems, we show that better Matrix Multiplication algorithms yield better 2-CSP Optimization algorithms, focusing on the case of MIN-BISECTION: given a graph on 2k nodes, partition the nodes into two parts of k nodes such that the number of edges straddling the two parts is minimized. Namely, we show that if multiplication of n by n matrices is possible in (n^3)/f(n) time for some function f, then a MIN-BISECTION of a graph with n nodes can be found in roughly (2^n)/f(2^{n/3}) time. In particular, the n^{2.376} matrix multiplication algorithm of Coppersmith and Winograd implies that MIN-BISECTION can be solved in 2^{.792n} time. Prior to our work, no improvement over brute-force search (2^n time) was known for solving 2-CSP Optimization exactly.