nils-herrmann/clean_scirepeval huggingface dataset:
Haystack : Per-User Information Environments MIT 9904-08 Proposal for 1999-2000 Funding

The World-Wide Web will soon be a powerful and dynamic replacement for today’s libraries and museums—public repositories of communal knowledge. But is this enough? Is this all that the electronic infrastructure can be? Libraries are huge, filled with masses of data irrelevant to any query. They are impersonal, presenting every user with the same information regardless of their background and interests. For these reasons, libraries are typically the last place we turn in seeking information. We start closer to home, with our own bookshelves. These are hand-selected and customorganized collections of the information most relevant to us as individuals. If we cannot find what we seek on our own bookshelves, we turn next to colleagues, friends, and associates---trusted members of communities with interests common to ours. It is only after exhausting these resources that we go to the library.
Fast Connected Components Algorithms for the EREW PRAM

We present fast and efficient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm runs in O(log n) time using $(m+n^{1+\epsilon})/\log n$ EREW processors (for any fixed $\epsilon>0$). A variant uses (m+n)/log n processors and runs in O(log n log log n) time. A deterministic version of the algorithm runs in $O(\log^{1.5}n)$ time using m+n EREW processors.
A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem

The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is $\SP$-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and $1/\epsilon$ an estimate for the failure probability that is accurate to within a relative error of $1\pm\epsilon$ with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described.
Approximate graph coloring by semidefinite programming

We consider the problem of coloring <italic>k</italic>-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on <italic>n</italic> vertices with min{<italic>O</italic>(Δ<supscrpt>1/3</supscrpt> log<supscrpt>1/2</supscrpt> Δ log <italic>n</italic>), <italic>O</italic>(<italic>n</italic><supscrpt>1/4</supscrpt> log<supscrpt>1/2</supscrpt> <italic>n</italic>)} colors where Δ is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of <italic>n</italic>, this marks the first nontrivial approximation result as a function of the maximum degree Δ. This result can be generalized to <italic>k</italic>-colorable graphs to obtain a coloring using  min{<italic>O</italic>(Δ<supscrpt>1-2/<italic>k</italic></supscrpt> log<supscrpt>1/2</supscrpt> Δ log <italic>n</italic>), <italic>O</italic>(<italic>n</italic><supscrpt>1−3/(<italic>k</italic>+1)</supscrpt> log<supscrpt>1/2</supscrpt> <italic>n</italic>)} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for <italic>semidefinite optimization problems</italic>, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovász &thgr;-function. We show lower bounds on the gap between the optimum solution of our semidefinite  program and the actual chromatic number; by duality this also demonstrates interesting new facts about the &thgr;-function.
Random sampling and greedy sparsification for matroid optimization problems

Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Application of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by agreedy algorithm that grows an independent set into an optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a givenfixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems.
A polynomial-time approximation scheme for weighted planar graph TSP

Given a planar Rraph on n nodes with costs (weights) on its edges,define ;he distance between nodes i &d 2 as’ the length of the shortest path between i and i. Consider this as &I instance of me& TSP. For any E > 6, our algorithm finds a salesman tour of total cost at most (1 + E) times optimal in time n”(llea). We also present a quasi-polynomial time algorithm for the Steiner version of this problem.
Finding maximum flows in undirected graphs seems easier than bipartite matching

Consider an n-vertex, m-edge, undirected graph with maximum flow value v. We give a method to find augmenting paths in such a graph in amortized sub-linear (O(npv)) time per path. This lets us improve the time bound of the classic augmenting path algorithm to O(m+ nv3=2) on simple graphs. The addition of a blocking flow subroutine gives a simple, deterministic O(nm2=3v1=6)-time algorithm. We also use our technique to improve known randomized algorithms, giving O(m+nv5=4)-time and O(m+n11=9v)-time algorithms for capacitated undirected graphs. For simple graphs, in which v n, the last bound is O(n2:2), improving on the best previous bound of O(n2:5), which is also the best known time bound for bipartite matching.
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (Extended Version)

We present a unified framework for designing polynomial time approximation schemes (PTASs) for ``dense'''' instances of many $\NP$-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum $k$-way cut with and without specified terminals, and maximum 3-satisfiability. By dense graphs we mean graphs with minimum degree $\Omega(n)$, although %\editsmall{some of our algorithms work}{ our algorithms solve most of these problems so long as the average degree is $\Omega(n)$. Denseness for non-graph problems is defined similarly. The unified framework begins with the idea of {\em exhaustive sampling:} picking a small random set of vertices, guessing where they go on the optimum solution, and then using their placement to determine the placement of everything else. The approach then develops into a PTAS for approximating certain {\em smooth\/} integer programs where the objective function and the constraints are ``dense'''' polynomials of constant degree.
Better random sampling algorithms for flows in undirected graphs

We present better random sampling algorithms for maximum flows in undirected graphs. Our algorithms apply to capacitated or uncapacitated graphs, and find a maximum flow of value v in ~ O(pmnv) time. This improves on a previous bound of ~ O(m2=3n1=3v) given by the author recently, which in turn improved on the O(mv) time bound for a typical augmenting path algorithm. In uncapacitated graphs without parallel edges, the bound is no worse than ~ O(n5=2). We give another algorithm that finds a (1 ) times maximum flow in time ~ O(mpn= ), regardless of v.
Techniques for Scheduling with Rejection

We consider the general problem of scheduling a set of jobs where we may choose not to schedule certain jobs, and thereby incur a penalty for each rejected job. More specifically, we focus on choosing a set of jobs to reject and constructing a schedule for the remaining jobs so as to optimize the sum of the weighted completion times of the jobs scheduled plus the sum of the penalties of the jobs rejected. 
 
We give several techniques for designing scheduling algorithms under this criterion. Many of these techniques show how to reduce a problem with rejection to a (potentially more complex) scheduling problem without rejection. Some of the reductions are based on general properties of certain kinds of linear-programming relaxations of optimization problems, and therefore are applicable to problems outside of scheduling; we demonstrate this by giving an approximation algorithm for a variant of the facility-location problem. 
 
In the last section of the paper we consider a different notion of rejection in the context of scheduling: scheduling jobs with due dates so as to maximize the number of jobs that complete by their due dates, or equivalently to minimize the number of jobs that do not complete by their due date and that thus can be considered "rejected." We investigate the approximability of a simple version of this problem, giving approximation algorithms and characterizing integrality gaps of a class of linear-programming relaxations.
Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web

We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for use with very large networks such as the Internet, where delays caused by hot spots can be severe, and where it is not feasible for every server to have complete information about the current state of the entire network. The protocols are easy to implement using existing network protocols such as TCP/IP, and require very little overhead. The protocols work with local control, make efficient use of existing resources, and scale gracefully as the network grows. Our caching protocols are based on a special kind of hashing that we call consistent hashing. Roughly speaking, a consistent hash function is one which changes minimally as the range of the function changes. Through the development of good consistent hash functions, we are able to develop caching protocols which do not require users to have a current or even consistent view of the network. We believe that consistent hash functions may eventually prove to be useful in other applications such as distributed name servers and/or quorum systems.
An NC Algorithm for Minimum Cuts

We show that the minimum-cut problem for weighted undirected graphs can be solved in $\NC$ using three separate and independently interesting results. The first is an $(m^2/n)$-processor $\NC$ algorithm for finding a $(2+\epsilon)$-approximation to the minimum cut. The second is a randomized reduction from the minimum-cut problem to the problem of obtaining a $(2+\epsilon)$-approximation to the minimum cut. This reduction involves a natural combinatorial set-isolation problem that can be solved easily in $\RNC$. The third result is a derandomization of this $\RNC$ solution that requires a combination of two widely used tools: pairwise independence and random walks on expanders. We believe that the set-isolation approach will prove useful in other derandomization problems. 
The techniques extend to two related problems: we describe $\NC$ algorithms finding minimum $k$-way cuts for any constant $k$ and finding all cuts of value within any constant factor of the minimum. Another application of these techniques yields an $\NC$ algorithm for finding a {\em sparse $k$-connectivity certificate} for all polynomially bounded values of $k$. Previously, an $\NC$ construction was only known for polylogarithmic values of $k$.
Implementing a fully polynomial time approximation scheme for all terminal network reliability

The classic all-terminal network reliability problem posits a graph, each of whose edges fails (disappears) independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. The practical applications of this question to communication networks are obvious, and the problem has therefore been the subject of a great deal of study. Since it is tjp-complete, and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. A comprehensive survey can be found in [Co187]. The first author recently presented an algorithm for approximating the probability of network disconnection under random edge failures. In this paper, we report on our experience implementing this algorithm. Our implementation shows that the algorithm is practical on networks of moderate size, and indeed works better than the theoretical bounds predict. Part of this improvement arises from heuristic modifications to the theoretical algorithm, while another part suggests that the theoretical running time analysis of the algorithm might not be tight. Based on our observation of the implementation, we were able to devise analytic explanations of at least some of the improved performance. As one example, we formally prove the accuracy of a simple heuristic approximation for the reliability. We also discuss other questions raised by the implementation which might be susceptible to analysis.
Distributed Job Scheduling in Rings

We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithm must balance computational load and communication time. The algorithm is simple, requires no global control, and yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments which suggest better performance than does our worst-case analysis.
Near-optimal intraprocedural branch alignment

Branch alignment reorders the basic blocks of a program to minimize pipeline penalties due to control-transfer instructions. Prior work in branch alignment has produced useful heuristic methods. We present a branch alignment algorithm that usually achieves the minimum possible pipeline penalty and on our benchmarks averages within 0.3% of a provable optimum. We compare the control penalties and running times of our algorithm to an older, greedy approach and observe that both the greedy method and our method are close to the lower bound on control penalties, suggesting that greedy is good enough. Surprisingly, in actual execution our method produces programs that run noticeably faster than the greedy method. We also report results from training and testing on different data sets, validating that our results can be achieved in real-world usage. Training and testing on different data sets slightly reduced the benefits from both branch alignment algorithms, but the ranking of the algorithms does not change, and the bulk of the benefits remain.
Experimental study of minimum cut algorithms

Recently, several new algorithms have been developed for the minimum cut problem that substantially improve worst-case time bounds for the problem. These algorithms are very different from the earlier ones and from each other. We conduct an experimental evaluation of the relative performance of these algorithms. In the process, we develop heuristics and data structures that substantially improve practical performance of the algorithms. We also develop problem families for testing minimum cut algorithms. Our work leads to a better understanding of practical performance of the minimum cut algorithms and produces very efficient codes for the problem.
Using random sampling to find maximum flows in uncapacitated undirected graphs

We present new algorithms, based on random sampling, that find maximum flows in undirected uncapacitated graphs. Our algorithms dominate augmenting paths over all parameter values (number of vertices and edges and flow value). They also dominate blocking flows over a large range of parameter values. Furthermore, they achieve time bounds on graphs with parallel (equivalently, capacitated) edges that previously could only be achieved on graphs without them. The key contribution of this paper is to demonstrate that such an improvement is possible. This shows that augmenting paths and blocking flows are non-optimal, and reopens the question of how fast we can find a maximum flow. We improve known time bounds by only a small (but polynomial) factor, and the complicated nature of our algorithms suggests they will not be practical. A new idea of our algorithm is to find flow by diminishing cuts instead of augmenting paths. Rather than finding a way to push flow from the source to the sink, we identify and delete edges that are not needed in a maximum flow. When no more edges can be deleted, we know that every remaining edge must be saturated to give a maximum flow.
Approximating s-t minimum cuts in Õ(n2) time

We improve on random sampling techniques for approximately solving problems that involve cuts in graphs. We give a lineartime construction that transforms any graph on n vertices into anO(n log n)-edge graph on the same vertices whose cuts have approximately the same value as the original graph’s. In this new graph, for example, we can run the ~ O(mn)-time maximum flow algorithm of Goldberg and Tarjan to find an s–tminimum cut in ~ O(n2) time. This corresponds to a (1 + )-times minimum s–t cut in the original graph. In a similar way, we can approximate a sparsest cut in ~ O(n2) time.
A new approach to the minimum cut problem

This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in <italic>O(n<supscrpt>2</supscrpt>log<supscrpt>3</supscrpt>n)</italic> time, a significant improvement over the previous <italic>O˜(mn)</italic> time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in <italic>RNC</italic> with <italic>n<supscrpt>2</supscrpt></italic> processors; this gives the first proof   that the minimum cut problem can be solved in <italic>RNC</italic>. The algorithm does more than find a single minimum cut; it finds all of them.
With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of α of the minimum cut's in expected <italic>O˜(n<supscrpt>2α</supscrpt>)</italic> time, or in <italic>RNC</italic> with <italic>n<supscrpt>2α</supscrpt></italic> processors. The problem of finding a minimum multiway cut of graph into <italic>r</italic> pieces is solved in expected <italic>O˜(n<supscrpt>2(r-1)</supscrpt>)</italic> time, or in <italic>RNC</italic> with <italic>n<supscrpt>2(r-1)</supscrpt></italic> processors. The “trace” of the    algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representing for minimum cuts.
Minimum cuts in near-linear time

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a random- ized (Monte Carlo) algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log 3 n) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n 2 log n) time. This variant has an optimal 51# parallelization.
Polynomial time approximation schemes for dense instances of NP-hard problems

We present a unified framework for designing polynomial time approximation schemes (PTASs) for “dense” instances of many NP-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specified terminals, and maximum 3-satisfiability. By dense graphs we mean graphs with minimum degree Ω(n), although our algorithms solve most of these problems so long as the average degree is Ω(n). Denseness for non-graph problems is defined similarly. The unified framework begins with the idea of exhaustive sampling: picking a small random set of vertices, guessing where they go on the optimum solution, and then using their placement to determine the placement of everything else. The approach then develops into a PTAS for approximating certain smooth integer programs where the objective function and the constraints are “dense” polynomials of constant degree.
Performance-Driven Routing Tree Design

Analysis of Elmore delay in distributed RC tree structures shows the influence of both tree cost and tree radius on signal delay in VLSI interconnects. We give new and efficient interconnection tree constructions that smoothly combine the minimum cost and the minimum radius objectives, by combining respectively optimnl algorithms due to Prim and Dijkstra. Previous "shallow-light" techniques (Z), (31, (81, (131 are both less direct and less effective: in practice, our methods achieve uniformly superior cost-radius tradeoffs. Timing simulations for a range of IC and MCM interconnect technologies show that our wirelength savings yield reduced signal delays when compared to shallow-light or standard minimum spanning tree and Steiner tree routing.