Ece Gelal, Gentian Jakllari, Srikanth V. Krishnamurthy, Neal E. Young
Abstract—With directional antennas, it is extremely important that a node maintains information with regards to the positions of its neighbors. This would allow the node to “track ” the...
Online Medians via Online Bribery (Extended Abstract) (2009)
Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young
We then consider the competitive ratio with respect to size. An algorithm is s-size-competitive if, for each k, the cost of Fk is at most the minimum cost of any set of k facilities, while the size...
Ece Gelal, Gentian Jakllari, Srikanth V. Krishnamurthy, Neal E. Young
Abstract — Our objective in this paper is to design topology control algorithms such that (i) nodes have low degree and (ii) paths in the network have few hops. Low node degree is desirable in...
Ece Gelal, Gentian Jakllari, Srikanth V. Krishnamurthy, Neal E. Young
Abstract—Our objective in this paper is to design topology control algorithms such that (i) nodes have low degree and (ii) paths in the network have few hops. Low node degree is desirable in...
Ece Gelal, Gentian Jakllari, Srikanth V. Krishnamurthy, Neal E. Young
Abstract—With directional antennas, it is extremely important that a node maintains information with regards to the positions of its neighbors. This would allow the node to “track ” the...
Ece Gelal, Gentian Jakllari, Srikanth V. Krishnamurthy, Neal E. Young
Abstract—With directional antennas, it is extremely important that a node maintains information with regards to the positions of its neighbors. This would allow the node to “track ” the...
Ece Gelal, Gentian Jakllari, Srikanth V. Krishnamurthy, Neal E. Young
Abstract—Our objective in this paper is to design topology control algorithms such that (i) nodes have low degree and (ii) paths in the network have few hops. Low node degree is desirable in...
Oblivious Medians Via Online Bidding (Extended Abstract) (2008)
Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young
Abstract. Following Mettu and Plaxton [22, 21], we study oblivious algorithms for the k-medians problem. Such an algorithm produces an incremental sequence of facility sets. We give improved...
Sequential, Parallel, Online, and Distributed Covering (2008)
Koufogiannakis, Christos, Young, Neal E.
The paper presents new d-approximation algorithms for covering problems, where d is the maximum number of variables on which any constraint depends (generalizing 2-approximation algorithms for Vertex...
Qi Fu, Elizabeth Bent, James Borneman, Marek Chrobak, Neal E. Young, Qi Fu, ...
We study the problem of selecting control clones in DNA array hybridization experiments. The problem arises in the OFRG method for analyzing microbial communities. The OFRG method performs...
Servings per container 5 (2008)
Neal E. Young, Servings Per Container, Vitamin C Iron, Daily Value
Marek is being punished. He can eat only bacon, beans, and beets! Can Marek get enough of what he needs without getting too much of what he doesn’t? 2
© 2004 INFORMS Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut (2008)
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k ≥ 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others....
Cross-input Amortization Captures the Diffuse Adversary (2008)
Koutsoupias and Papadimitriou recently raised the question of how well deterministic on-line paging algorithms can do against a certain class of adversarially biased random inputs [3]. Such an input...
Beating Simplex for Fractional Packing and Covering Linear Programs (2008)
Koufogiannakis, Christos, Young, Neal E.
We give an approximation algorithm for packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the...
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The...
Mordecai J. Golin, Claire Kenyon, Neal E. Young
In the standard Human coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must...
K-Medians, Facility Location, and the Cherno-Wald Bound (2007)
We study the general (non-metric) facility-location and weighted k-medians problems, as well as the fractional facility-location and unweighted k-medians problems. We describe a natural randomized...
Neal E. Young, Robert E. Tarjan, James B. Orlin
We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum-balance algorithm to...
Competitive Paging Algorithms Amos Fiat 1 (2007)
Richard M. Karp, Michael Luby, Lyle A. Mcgeoch, Daniel D. Sleator, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...
The reverse greedy algorithm for the metric k-median problem (2005)
Chrobak, Marek, Kenyon, Claire, Young, Neal E.
The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the resulting total...
Oblivious Medians via Online Bidding (2005)
Chrobak, Marek, Kenyon, Claire, Noga, John, Young, Neal E.
Following Mettu and Plaxton, we study online algorithms for the k-medians problem. Such an algorithm must produce a nested sequence F_1\subseteq F_2\subseteq...\subseteq F_n of sets of facilities....
Designing Multi-Commodity Flow Trees (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal E.
The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands. This paper considers the...
A New Operation on Sequences: the Boustrouphedon Transform (2002)
Millar, Jessica, Sloane, N. J. A., Young, Neal E.
A generalization of the Seidel-Entringer-Arnold method for calculating the alternating permutation numbers (or secant-tangent numbers) leads to a new operation on integer sequences, the Boustrophedon...
This paper gives a lower bound on the complexity of epsilon-approximately solving a packing or covering problem using a certain class of ``Lagrangian-relaxation'' algorithms: any such algorithm,...
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut (2002)
Karger, David, Klein, Phil, Stein, Cliff, Thorup, Mikkel, Young, Neal E.
The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even...
Randomized Rounding without Solving the Linear Program (2002)
Randomized rounding is a standard method, based on the probabilistic method, for designing combinatorial approximation algorithms. In Raghavan's seminal paper introducing the method (1988), he...
Sequential and Parallel Algorithms for Mixed Packing and Covering (2002)
Mixed packing and covering problems are problems that can be formulated as linear programs using only non-negative coefficients. Examples include multicommodity network flow, the Held-Karp lower...
Approximating the Minimum Equivalent Digraph (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal E.
The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is NP-hard. This paper...
Orienting Graphs to Optimize Reachability (2002)
Hakimi, S. L., Schmeichel, E., Young, Neal E.
The paper focuses on two problems: (i) how to orient the edges of an undirected graph in order to maximize the number of ordered vertex pairs (x,y) such that there is a directed path from x to y, and...
Low-Degree Spanning Trees of Small Weight (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal E.
The degree-d spanning tree problem asks for a minimum-weight spanning tree in which the degree of each vertex is at most d. When d=2 the problem is TSP, and in this case, the well-known Christofides...
Balancing Minimum Spanning and Shortest Path Trees (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal E.
This paper give a simple linear-time algorithm that, given a weighted digraph, finds a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm...
K-Medians, Facility Location, and the Chernoff-Wald Bound (2002)
The paper gives approximation algorithms for the k-medians and facility-location problems (both NP-hard). For k-medians, the algorithm returns a solution using at most ln(n+n/epsilon)k medians and...
Huffman Coding with Unequal Letter Costs (2002)
Golin, Mordecai, Kenyon, Claire, Young, Neal E.
In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding...
Prefix Codes: Equiprobable Words, Unequal Letter Costs (2002)
Golin, Mordecai, Young, Neal E.
Describes a near-linear-time algorithm for a variant of Huffman coding, in which the letters may have non-uniform lengths (as in Morse code), but with the restriction that each word to be encoded has...
Competitive Paging Algorithms (2002)
Fiat, Amos, Karp, Richard, Luby, Mike, McGeoch, Lyle, Sleator, Daniel, Young, Neal E.
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. This paper introduces the marking algorithm, a simple randomized...
The K-Server Dual and Loose Competitiveness for Paging (2002)
This paper has two results. The first is based on the surprising observation that the well-known ``least-recently-used'' paging algorithm and the ``balance'' algorithm for weighted caching are...
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (2002)
Fekete, S., Khuller, S., Klemmstein, M., Raghavachari, B., Young, Neal E.
The problem considered is the following. Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, compute a low-weight spanning tree such that the...
Lecture Notes on Evasiveness of Graph Properties (2002)
Lovasz, Laszlo, Young, Neal E.
This report presents notes from the first eight lectures of the class Many Models of Complexity taught by Laszlo Lovasz at Princeton University in the fall of 1990. The topic is evasiveness of graph...
Approximation Algorithms for Covering/Packing Integer Programs (2002)
Kolliopoulos, Stavros G., Young, Neal E.
Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing min {c.x: x in Z^n_+, Ax > a, Bx < b, x < d}. We give a bicriteria-approximation...
On-Line End-to-End Congestion Control (2002)
Congestion control in the current Internet is accomplished mainly by TCP/IP. To understand the macroscopic network behavior that results from TCP/IP and similar end-to-end protocols, one main...
In the on-line file-caching problem problem, the input is a sequence of requests for files, given on-line (one at a time). Each file has a non-negative size and a non-negative retrieval cost. The...
Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory (2002)
Lipton, Richard, Young, Neal E.
Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. This paper gives an elementary proof that each player has a near-optimal mixed...
On-Line Paging against Adversarially Biased Random Inputs (2002)
In evaluating an algorithm, worst-case analysis can be overly pessimistic. Average-case analysis can be overly optimistic. An intermediate approach is to show that an algorithm does well on a broad...
Huffman coding with unequal letter costs (2002)
Golin, Mordecai J., Kenyon, Claire, Young, Neal E.
In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding...
On-line End-to-End Congestion Control (2002)
Congestion control in the current Internet is accomplished mainly by TCP/IP. To understand the macroscopic network behavior that results from TCP/IP and similar endto-end protocols, one main analytic...
Abstract Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory (2002)
Richard J. Lipton, Neal E. Young
Von Neumann’s Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. We show that each player has a near-optimal mixed strategy that chooses uniformly...
Huffman coding with unequal letter costs (2002)
Mordecai J. Golin, Claire Kenyon, Neal E. Young
In the standard Hu#man coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding...
On-line paging against adversarially biased random inputs (2002)
In evaluating an algorithm, worst-case analysis can be overly pessimistic. Average-case analysis can be overly optimistic. An intermediate approach is to show that an algorithm does well on a broad...
On-line paging against adversarially biased random inputs (2002)
Neal E. Young, H. Papadimitriou Ž
In evaluating an algorithm, worst-case analysis can be overly pessimistic. Average-case analysis can be overly optimistic. An intermediate approach shows that an algorithm does well on a broad class...
Sequential and parallel algorithms for mixed packing and covering (2001)
We describe sequential and parallel algorithms that approximately solve linear programs with no negative coefficients (a.k.a. mixed packing and covering problems). For explicitly given problems, our...
Tight approximation results for general covering integer programs (2001)
Stavros G. Kolliopoulos, Neal E. Young
In this paper we study approximation algorithms for solving a general covering integer program. An n-vector x of nonnegative integers is sought, which minimizes c T x; subject to Ax b; x d: The...
Sequential and parallel algorithms for mixed packing and covering (2001)
We describe sequential and parallel algorithms that approximately solve linear programs with no negative coefficients (a.k.a. mixed packing and covering problems). For explicitly given problems, our...
Observation of Changing Information Sources (2000)
Brian E. Brewington, Robert S. Gray, Clayton M. Okino, Cliord S. Stein, Neal E. Young, Brian E. Brewington, ...
Many modern information management tasks consist of an observer that must maintain current knowledge of a collection of changing information. The goal of this observer is to maintain acceptably...
Approximation algorithms for np-hard optimization problems (1999)
Philip N. Klein, Neal E. Young
copyright CRC press
Rounding algorithms for a geometric embedding of minimum multiway cut (1999)
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The...
Consider the following le caching problem: in response to a sequence of requests for les, where each le has a specied size and retrieval cost, maintain a cache of les of total size at most some...
Prasad Jayanti, Fillia Makedon, Aravind Srinivasan, Neal E. Young, Roger D. Sloboda, Stavros G. Kolliopoulos, ...
ii Network flow problems form a core area of Combinatorial Optimization. Their significance arises both from their very large number of applications and their theoretical importance. This thesis...
Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost, maintain a cache of files of total size at most...
A Codebook Generation Algorithm for Document Image Compression (1997)
Qin Zhang, John M. Danskin, Neal E. Young
compression
Orienting graphs to optimize reachability (1997)
Edward F. Schmeichel, Neal E. Young
It is well known that every 2-edge-connected graph can be oriented so that the resulting digraph is strongly connected. Here we study the problem of orienting a connected graph with cut edges in...
A Codebook Generation Algorithm for Document Image Compression (1997)
Qin Zhang, John M. Danskin, Neal E. Young
Pattern-matching based document compression systems rely on finding a small set of patterns that can be used to represent all of the ink in the document. Finding an optimal set of patterns is...
Performance evaluation of approximate priority queues (1996)
We report on implementation and a modest experimental evaluation of a recently introduced priority-queue data structure. The new data structure is designed to take advantage of fast operations on...
Performance Evaluation of Approximate Priority Queues (1996)
Yossi Matias, Suleyman Cenk Sahinalp, Neal E. Young
We report on implementation and a modest experimental evaluation of a recently introduced priority-queue data structure. The new data structure is designed to take advantage of fast operations on...
Randomized rounding without solving the linear program (1995)
We introduce a new technique called oblivious rounding---a variant of randomized rounding that avoids the bottleneck of first solving the linear program. Avoiding this bottleneck yields more...
Approximate data structures with applications (1994)
Yossi Matias, Jeffrey Scott Vitter, Neal E. Young
In this paper we introduce the notion of approximate data structures, in which a small amount of error is tolerated in the output. Approximate data structures trade error of approximation for faster...
Simple strategies for large zero-sum games with applications to complexity theory (1994)
Richard J. Lipton, Neal E. Young
Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. We show that each player has a near-optimal mixed strategy that chooses...
Approximate Data Structures with Applications (Extended Abstract) (1994)
Yossi Matias, Jeffrey Scott Vitter, Neal E. Young
) Yossi Matias y Jeffrey Scott Vitter z Neal E. Young x Abstract In this paper we introduce the notion of approximate data structures, in which a small amount of error is tolerated in the output....
Competitive Paging Algorithms (1991)
Amos Fiat, Richard M. Brp, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...
JOURNAL OF ALGORITHMS 12,685-699 (1991) Competitive Paging Algorithms (1988)
Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. Mcgeoch, Daniel D. Sleator, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...