The randtext package is a great random find in CTAN. Here is its description in full, but with an emphasis added by me:
The package provides a single macro \randomize{TEXT} that typesets the characters of TEXT in random order, such that the resulting output appears correct, but most automated attempts to read the file will misunderstand it.
This function allows one to include an email address in a TeX document and publish it online without fear of email address harvesters or spammers easily picking up the address.
The author is Charles Duan.
While you most certainly want to use this package for some protection, you should not rely solely on it. For a historical reason(*) , Adobe’s PDF library can easily extract an email address protected by this package. I don’t know about the top search engines, but I would expect their extractors to perform no worse.
(*) Basically, space characters need not exist after the TeX phase. They may instead exist as kerning and spacing information. Therefore, Adobe have an extraction routine that guesses the word breaks based on how the characters are spaced. In other words, the routine is literally “reading” the text from the rendering, just like any human!
Algorithms for 2-Route Cut Problems
Chandra Chekuri, UIUC
December 7, 2007, 3:30PM, Wean 7220
Abstract:
We study approximation algorithms for multi-route cut problems in undirected graphs. In these problems the goal is to find a minimum cost set of edges to be removed from a given graph such that the edge-connectivity (or node-connectivity) between certain pairs of nodes is reduced below a given threshold $K$. In the usual cut problems the edge connectivity is required to be reduced below $1$ (i.e. disconnected).
We consider the case of $K=2$ and obtain poly-logarithmic approximation algorithms for fundamental cut problems including single-source, multiway-cut, multicut, and sparsest cut. These cut problems are dual to multi-route flows that are of interest in fault-tolerant networks flows. Our results show that the flow-cut gap between $2$-route cuts and $2$-route flows is poly-logarithmic in undirected graphs with arbitrary capacities. $2$-route cuts are also closely related to well-studied feedback problems and we obtain algorithms for some new variants.
Our algorithms are based on a new randomized scaling procedure combined with known algorithms for standard (1-route) cut problems. Several open problems will be discussed.
Joint work with Sanjeev Khanna (U. Penn)
December 10, 2007
Matthew Streeter
3:30 PM, 4623 Wean Hall
Title: Using Online Algorithms to Solve NP-Hard Problems More Efficiently in Practice
Abstract:
This thesis develops online algorithms that can be used to solve a variety of NP-hard problems more efficiently in practice, by taking existing algorithms as input and adapting the algorithms to the sequence of problem instance(s) they are run on.
We first consider the following problem. We are given k algorithms, and are fed, one at a time, a sequence of problem instances to solve. We may solve each instance using any of the k algorithms, we may interleave the execution of the algorithms, and, if the algorithms are randomized, we may periodically restart them with a fresh random seed. We consider two objectives: minimizing the average CPU time required to solve the instances, and maximizing the number of instances solved in time at most T. We present an online algorithm that (asymptotically) performs near-optimally in terms of both objectives. In fact, this algorithm solves a more abstract online resource allocation problem, with applications to database query processing and sensor placement. Using data from eight recent solver competitions, we show that our online algorithm and its offline counterpart can be used to improve the performance of state-of-the-art solvers in a number of problem domains, including Boolean satisfiability, zero-one integer programming, constraint satisfaction, and theorem proving.
We next consider algorithms that solve an optimization problem by making a sequence of calls to a decision procedure that answers questions of the form “Is there a solution of cost at most k?” We present a principled approach to determining the questions to ask and the maximum time to spend waiting for an answer to each question. Applying our approach to recent algorithms for A.I. planning and job shop scheduling allows them to find approximately optimal solutions more quickly.
Lastly, we develop algorithms for solving the max k-armed bandit problem, a variant of the classical k-armed bandit problem in which one seeks to maximize the highest payoff received on any single trial, rather than the cumulative payoff. Our max k-armed bandit strategy can be used to effectively allocate trials among multi-start heuristics for the resource-constrained project scheduling problem.
Thesis Committee:
Stephen F. Smith, Chair
Avrim Blum
Tuomas Sandholm
John N. Hooker
Carla P. Gomes, Cornell University
Title: Induced subgraphs with distinct size or order
Speaker: Alexander Kostochka, University of Illinois at Urbana-Champaign
When: December 6, 16:30-17:30
Where: Wean Hall 5302
For a graph G, let \phi(G) denote the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G. Let hom(G) denote the maximum number of vertices in an induced clique or an induced independent set in G. An n-vertex graph is c-Ramsey, if hom(G) \leq c log n. Erdos, Faudree and Sos conjectured that for every positive constant c, there is a positive constant b = b(c) such that if G is a c-Ramsey graph on n vertices, then \phi(G) ≥ bn^{5/2}. They also proved the weaker lower bound Ω(n^{3/2}).
We prove the bound Ω(n^2) for the wider class of n-vertex graphs with average degree at least 0.001n and at most 0.999n. The order of magnitude of the bound cannot be improved in this class as shown, for example, by the complete bipartite n-vertex graphs.
This is joint work with N. Alon.
Who: Shuchi Chawla
Where: NSH 1507
When: 2007-12-05 12:00
Title: Bertrand Competition in Networks
Abstract:
The Internet is a unique modern artifact given its sheer size and the number of its users. Given its continuing distributed and ad-hoc evolution, there have been growing concerns about the effectiveness of its current routing protocols in finding good routes and ensuring quality of service. Imposing congestion-based and QoS-based prices on traffic has been suggested as a way of combating the ills of this distributed growth and selfish use of resources. Unfortunately, the effectiveness of such approaches relies on the cooperation of the multiple entities implementing them, namely the ISPs or Internet service providers. The goals of the ISPs do not necessarily align with the social objectives of efficiency and quality of service; their primary objective is to maximize their own profit. It is therefore imperative to study the following question: given a large combinatorial market such as the Internet, suppose that the owners of resources selfishly price their product to maximize their own profit, and consumers selfishly purchase resources to maximize their own utility, how does this effect the functioning of the market as a whole?
We study this problem in the context of a simple network pricing game, and analyze the performance of equilibria arising in this game as a function of the degree of competition in the game, the network topology, and the demand structure. Economists have traditionally studied such questions in single-item markets. It is well known, for example, that monopolies cause inefficiency in a market by charging high prices, whereas competition has the effect of driving prices down and operating efficiently. Our work extends the classical Bertrand model of competition from economics to the network setting. For example, we ask (and answer): is competition in a network enough to ensure efficient operation? does performance worsen as the number of monopolies grows? does the answer depend in an interesting way on the network topology and/or demand distribution?
This is joint work with Tim Roughgarden.
