Settling the Complexity of Computing Two-Player Nash Equilibria ∗ (2009)
Xi Chen, Xiaotie Deng, Shang-hua Teng
We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by...
Finding local communities in protein networks (2009)
Voevodski, Konstantin, Teng, Shang-Hua, Xia, Yu
Abstract Background Protein-protein interactions (PPIs) play fundamental roles in nearly all biological processes, and provide major insights into the inner workings of cells. A vast amount of PPI...
It is a common belief that computing a market equilibrium in Fisher's spending model is easier than computing a market equilibrium in Arrow-Debreu's exchange model. This belief is built on the fact...
Reducibility Among Fractional Stability Problems (2009)
Kintali, Shiva, Poplawski, Laura J., Rajaraman, Rajmohan, Sundaram, Ravi, Teng, Shang-Hua
In this paper, we resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be PPAD-complete, along with the...
Chen, Xi, Dai, Decheng, Du, Ye, Teng, Shang-Hua
We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility functions. In fact, our...
Decision trees are PAC-learnable from most product distributions: a smoothed analysis (2008)
Kalai, Adam Tauman, Teng, Shang-Hua
We consider the problem of PAC-learning decision trees, i.e., learning a decision tree over the n-dimensional hypercube from independent random labeled examples. Despite significant effort, no...
and Fixed Point Computation (2008)
Xi Chen, Xiaoming Sun, Shang-hua Teng
In this paper, we give a lower bound of Ω(n (d−1)/2) on the quantum query complexity for finding a fixed point of a discrete Brouwer function over grid [1: n] d. Our bound is nearly tight, as the...
Regression depth and center points (2008)
Nina Amenta, Marshall Bern, Shang-hua Teng
We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ⌈n/(d + 1)⌉, as had been conjectured by Rousseeuw and Hubert. Dually, for any...
Optimal Tree Contraction in the EREW Model Abstract (2008)
Gary L. Miller, Shang-hua Teng
A deterministic parallel algorithm for parallel tree contraction is presented in this paper. The algorithm takes T time and uses (P processors, where n the number of vertices in a tree using an...
Preference Games and Personalized Equilibria, with Applications to Fractional BGP (2008)
Poplawski, Laura J., Rajaraman, Rajmohan, Sundaram, Ravi, Teng, Shang-Hua
We study the complexity of computing equilibria in two classes of network games based on flows - fractional BGP (Border Gateway Protocol) games and fractional BBC (Bounded Budget Connection) games....
Spielman, Daniel A., Teng, Shang-Hua
We study the design of local algorithms for massive graphs. A local algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local...
Spectral Sparsification of Graphs (2008)
Spielman, Daniel A., Teng, Shang-Hua
We introduce a new notion of graph sparsificaiton based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate...
Alla Sheffer, Robert B. Haber, Shang-hua Teng
Layer based solutions for constrained space-time meshing Alper "Ung"or
Laoutaris, Nikolaos, Poplawski, Laura J., Rajaraman, Rajmohan, Sundaram, Ravi, Teng, Shang-Hua
Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game - we have a collection of n players or nodes each of whom...
Truthful Auctions with Optimal Profit (2008)
Pinyan Lu, Shang-hua Teng, Changyuan Yu
Abstract. We study the design of truthful auction mechanisms for maximizing the seller’s profit. We focus on the case when the auction mechanism does not have any knowledge of bidders ’...
Lectured Prof, Shang-hua Teng, Scribed Feifei Li
The above problem could be extended to the K-Nearest Neighbor problem as: Given any integer k, extends the above problem, Nk(pi) = set of k nearest neighbor. Having Nk(pi), we could get its K-Nearest...
Xi Chen, Xiaotie Deng, Shang-hua Teng
Abstract. A two-player game is sparse if most of its payoff entries are zeros. We show that the problem of computing a Nash equilibrium remains PPAD-hard to approximate in fully polynomial time for...
Abstract Subspace Gradient Domain Mesh Deformation (2008)
Jin Huang, Xiaohan Shi, Xinguo Liu, Kun Zhou, Li-yi Wei, Shang-hua Teng, ...
In this paper we present a general framework for performing constrained mesh deformation tasks with gradient domain techniques. We present a gradient domain technique that works well with a wide...
Truthful Auctions with Optimal Profit (2008)
Pinyan Lu, Shang-hua Teng, Changyuan Yu
Abstract. We study the design of truthful auction mechanisms for maximizing the seller’s profit. We focus on the case when the auction mechanism does not have any knowledge of bidders ’...
Marshall Bern, David Eppstein, Shang-hua Teng
We describe efficient PRAM algorithms for constructing unbalanced quadtrees, balanced quadtrees, and quadtree-based finite element meshes. Our algorithms take time O(log n) for point set input and...
Practical Human-Machine Identification over Insecure Channels (2007)
. Human-machine identification is an important problem in cryptography that has applications in network access, electronic commerce, and smart-card design. It is a hard problem largely because human...
Generate Good Mesh Respecting to Control Spacing (2007)
Xiang-yang Li, Peng-jun Wan, Shang-Hua Teng, Alper Ungor
This paper presents an efficient algorithm to generate a well-shaped and a well-conformed mesh respecting to a given control spacing
Generate Good Mesh Efficiently (2007)
Xiang-yang Li, Peng-jun Wan, Shang-Hua Teng, Alper Ungor
this paper, we show
Recovering Mesh Geometry from a Stiffness Matrix (2007)
Andreas Stathopoulos, Shang-Hua Teng
. We introduce the following class of mesh recovery problems: Given a stiffness matrix A and a PDE, construct a mesh M such that the finite-element formulation of the PDE over M is A. We show, under...
Alan Edelman, Robert Schreiber, Hewlett Packard, Shang-hua Teng, U. Minnesota
These lecture notes #under development and constant revision, like the #eld itself # have been used at MIT in a graduate course #rst o#ered by Alan Edelman and Shang-Hua Teng during the spring of...
Point placement for meshless methods using sphere packing and advancing front methods (2007)
Xiang-yang Li, Shang-hua Teng, Alper Üngör
For simulation of numerical problems, meshless methods have emerged as an alternative to mesh based methods and become popular due to several reasons. Primarily, mesh generation is a difficult...
Anja Feldmann, Ming-yang Kao, Shang-hua Teng
We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific...
Yu Charlie Hu, Yu Charlie Hu, Shang-hua Teng, Shang-hua Teng, S. Lennart Johnsson, S. Lennart Johnsson
We present a data-parallel, High Performance Fortran (HPF) implementation of the geometric partitioning algorithm. The geometric partitioning algorithm has provably good partitioning quality. To our...
Optimal Cache-Oblivious Mesh Layouts (2007)
Bender, Michael A., Kuszmaul, Bradley C., Teng, Shang-Hua, Wang, Kebin
This paper shows how to generate a cache-oblivious memory layout of a well-shaped finite-element mesh G. This cache-oblivious mesh layout enables asymptotically optimal mesh updates, in which each...
Settling the Complexity of Computing Two-Player Nash Equilibria (2007)
Chen, Xi, Deng, Xiaotie, Teng, Shang-Hua
We settle a long-standing open question in algorithmic game theory. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD...
Games on the Sperner Triangle (2007)
We create a new two-player game on the Sperner Triangle based on Sperner's lemma. Our game has simple rules and several desirable properties. First, the game is always certain to have a winner....
Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation (2007)
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains...
A bounded-degree network formation game (2007)
Laoutaris, Nikolaos, Rajaraman, Rajmohan, Sundaram, Ravi, Teng, Shang-Hua
Motivated by applications in peer-to-peer and overlay networks we define and study the \emph{Bounded Degree Network Formation} (BDNF) game. In an $(n,k)$-BDNF game, we are given $n$ nodes, a bound...
Local computation of pagerank contributions (2007)
Reid Andersen, Christian Borgs, Jennifer Chayes, John Hopcraft, Vahab S. Mirrokni, Shang-hua Teng
Abstract. Motivated by the problem of detecting link-spam, we consider the following graph-theoretic primitive: Given a webgraph G, a vertex v in G, and a parameter δ ∈ (0, 1), compute the set of...
Local computation of pagerank contributions (2007)
Reid Andersen, Christian Borgs, Jennifer Chayes, John Hopcraft, Vahab S. Mirrokni, Shang-hua Teng
Abstract. Motivated by the problem of detecting link-spam, we consider the following graph-theoretic primitive: Given a webgraph G, a vertex v in G, and a parameter δ ∈ (0, 1), compute the set of...
07391 Abstracts Collection -- Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Dietzfelbinger, Martin, Teng, Shang-Hua, Upfal, Eli, Vöcking, Berthold
From 23.09.2007 to 28.09.2007, the Dagstuhl Seminar 07391 "Probabilistic Methods in the Design and Analysis of Algorithms''was held in the International Conference and Research Center (IBFI), Schloss...
Spielman, Daniel A., Teng, Shang-Hua
We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant $n$-by-$n$ matrix $A$ with $m$ non-zero entries and an $n$-vector $\bb$, produces an $\xxtil $ such that...
On the Approximation and Smoothed Complexity of Leontief Market Equilibria (2006)
Huang, Li-Sha, Teng, Shang-Hua
We show that the problem of finding an \epsilon-approximate Nash equilibrium of an n by n two-person games can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a...
Computing Nash Equilibria: Approximation and Smoothed Complexity (2006)
Chen, Xi, Deng, Xiaotie, Teng, Shang-Hua
We show that the BIMATRIX game does not have a fully polynomial-time approximation scheme, unless PPAD is in P. In other words, no algorithm with time polynomial in n and 1/\epsilon can compute an...
Market equilibria with hybrid linear-Leontief utilities (2006)
Xi Chen, Li-sha Huang, Shang-hua Teng
Abstract. We introduce a new family of utility functions for exchange markets. This family provides a natural and ”continuous ” hybridization of the traditional linear and Leontief utilities and...
Michael Elkin, Daniel A. Spielman, Y. Emek, Shang-hua Teng
as a subgraph a spanning tree into which the edges of G can be embedded with average stretch exp � O ( √ log n log log n) � , and that there exists an n-vertex graph G such that all its...
Lower-stretch spanning trees (2005)
Michael Elkin, Daniel A. Spielman, Yuval Emek, Shang-hua Teng
We show that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch O(log 2 n log log n). Moreover, we show that this...
On trip planning queries in spatial databases (2005)
Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, Shang-hua Teng
In this paper we discuss a new type of query in Spatial Databases, called the Trip Planning Query (TPQ). Given a set of points of interest P in space, where each point belongs to a specific category,...
On trip planning queries in spatial databases (2005)
Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, Shang-hua Teng
Abstract. In this paper we discuss a new type of query in Spatial Databases,called the Trip Planning Query (TPQ). Given a set of points of interest P inspace, where each point belongs to a specific...
On trip planning queries in spatial databases (2005)
Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, Shang-hua Teng
Abstract. In this paper we discuss a new type of query in Spatial Databases, called the Trip Planning Query (TPQ). Given a set of points of interest ¢ in space, where each point belongs to a...
On trip planning queries in spatial databases (2005)
Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, Shang-hua Teng
Abstract. In this paper we discuss a new type of query in Spatial Databases, called the Trip Planning Query (TPQ). Given a set of points of interest P in space, where each point belongs to a specific...
Lower-Stretch Spanning Trees (2004)
Elkin, Michael, Emek, Yuval, Spielman, Daniel A., Teng, Shang-Hua
We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).
Spielman, Daniel A., Teng, Shang-Hua
This paper has been divided into three papers. arXiv:0809.3232, arXiv:0808.4134, arXiv:cs/0607105
Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$ (2003)
Spielman, Daniel A., Teng, Shang-Hua
We present a linear-system solver that, given an $n$-by-$n$ symmetric positive semi-definite, diagonally dominant matrix $A$ with $m$ non-zero entries and an $n$-vector $\bb $, produces a vector...
Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices (2003)
Sankar, Arvind, Spielman, Daniel A., Teng, Shang-Hua
Let $\orig{A}$ be any matrix and let $A$ be a slight random perturbation of $\orig{A}$. We prove that it is unlikely that $A$ has large condition number. Using this result, we prove it is unlikely...
Smoothed Analysis of Interior-Point Algorithms: Condition Number (2003)
Dunagan, John, Spielman, Daniel A., Teng, Shang-Hua
We show that the smoothed complexity of the logarithm of Renegar's condition number is O(log (n/sigma)).
Smoothed Analysis of Interior-Point Algorithms: Termination (2003)
Spielman, Daniel A., Teng, Shang-Hua
We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by Dunagan, Spielman...
Daniel A. Spielman, Shang-hua Teng
We introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over...
Smoothed analysis of algorithms (2002)
Spielman, Daniel A., Teng, Shang-Hua
Spielman and Teng introduced the smoothed analysis of algorithms to provide a framework in which one could explain the success in practice of algorithms and heuristics that could not be understood...
Parallel Delaunay Refinement: Algorithms and Analyses (2002)
Spielman, Dan A., Teng, Shang-hua, Ungor, Alper
In this paper, we analyze the complexity of natural parallelizations of Delaunay refinement methods for mesh generation. The parallelizations employ a simple strategy: at each iteration, they choose...
Smoothed Analysis of Renegar's Condition Number for Linear Programming (2002)
John Dunagan, Daniel A. Spielman, Shang-hua Teng
For any linear program, we show that a slight random relative perturbation of that linear program has small condition number with high probability. Following [ST01], we call this smoothed analysis of...
John Dunagan, Daniel A. Spielman, Shang-hua Teng
For any linear program, we show that a slight random relative perturbation of that linear program has small condition number with high probability. Following [ST01], we call this smoothed analysis of...
Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (2001)
Spielman, Daniel A., Teng, Shang-Hua
We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected...
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time (2001)
Daniel A. Spielman, Shang-hua Teng
Abstract. We introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the...
Cheng, Siu-Wing, Dey, Tamal K., Edelsbrunner, Herbert, Facello, Michael A., Teng, Shang-Hua
A silver is a tetrahedron whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Silvers are notoriously common in...
Smoothing and Cleaning up Slivers (2000)
Herbert Edelsbrunner, Xiang-yang Li, Gary Miller, Andreas Stathopoulos, Dafna Talmor, Shang-Hua Teng, ...
A sliver is a tetrahedron whose four vertices lie close to a plane and whose perpendicular projection to that plane is a convex quadrilateral with no short edge. Slivers are both undesirable and...
Regression Depth and Center Points (2000)
Nina Amenta, Marshall Bern, David Eppstein, Shang-Hua Teng, N. Amenta, M. Bern, ...
. We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least #n/(d + 1)#, as had been conjectured by Rousseeuw and Hubert. Dually, for any...
Coarsening, Sampling, And Smoothing: Elements Of The Multilevel Method (1999)
. The multilevel method has emerged as one of the most effective methods for solving numerical and combinatorial problems. It has been used in multigrid, domain decomposition, geometric search...
Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-Hua Teng
A sliver is a tetrahedron whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in...
Biting: Advancing Front Meets Sphere Packing (1999)
Xiang-yang Li, Shang-Hua Teng, Alper Üngör
. A key step in the finite element method is to generate a high quality mesh that is as small as possible for an input domain. Several meshing methods and heuristics have been developed and...
Siu-wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-hua Teng
A sliver is a tetrahedron whose four vertices lie close to a plane and whose projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional...
Xiang-yang Li, Shang-Hua Teng, Alper Üngör
. We present an efficient 3D meshing algorithm which combines the merits of two popular meshing methods, advancing front and sphere packing methods. In particular, it inherits the practicality and...
Biting Ellipses to Generate Anisotropic Mesh (1999)
Xiang-yang Li, Shang-Hua Teng, Alper Üngör
. In numerical simulation where the underlying function is strongly directional, it is desirable to use a mesh that is adaptive both in size and in shape. In such simulation, a metric tensor is used...
Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-Hua Teng
A sliver is a tetrahedron whose four vertices lie close to a plane and whose projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional...
Regression Depth and Center Points (1998)
Amenta, Nina, Bern, Marshall, Eppstein, David, Teng, Shang-Hua
We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any...
A Wiley-Interscience Publication (1998)
Advisors Prof, Shang-hua Teng, Prof Jeff Erickson, Advisor Prof, Ali Yazıcı, Advisors Prof, ...
Deisgn and analysis of algorithms, computational geometry, mesh generation, bio-geometric modeling,
Dynamic Load Balancing for Parallel Adaptive Mesh Refinement (1998)
Adaptive mesh refinement is a key problem in large-scale numerical calculations. The need of adaptive mesh refinement could introduce load imbalance among processors, where the load measures the...
Simultaneous Refinement and Coarsening for Adaptive Meshing (1998)
Xiang-yang Li, Shang-Hua Teng, Alper Üngör
. In numerical simulation of the combustion process and microstructural evolution, we need to consider the adaptive meshing problem for a domain that has a moving boundary. During the simulation, the...
Regression Depth and Center Points (1998)
Nina Amenta, Marshall Bern, David Eppstein, Shang-Hua Teng
this paper is on the xxx.lanl.gov e-print server, cs.CG/9809037.
Simultaneous Refinement and Coarsening: Adaptive Meshing with Moving Boundaries (1998)
Xiang-yang Li, Shang-Hua Teng, Alper Üngör, Alper Ungor
. In the numerical simulation of the combustion process and microstructural evolution, we need to consider the adaptive meshing problem for a domain with a moving boundary, in which, the submesh in...
Optimal On-line Scheduling of Parallel Jobs with Dependencies (1998)
Anja Feldmann, Ming-yang Kao, Jirí Sgall, Shang-Hua Teng
We study the following general on-line scheduling problem. Parallel jobs arrive on a parallel machine dynamically according to the dependencies between them. Each job requests a certain number of...
Min-Max-Boundary Domain Decomposition (1998)
Marcos Kiwi, Daniel A. Spielman, Shang-Hua Teng
Domain decomposition is one of the most effective and popular parallel computing techniques for solving large scale numerical systems. In the special case when the amount of computation in a...
Optimal on-line scheduling of parallel jobs with dependencies (1998)
Anja Feldmann, Ming-yang Kao, Shang-hua Teng
Abstract We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a...
A data-parallel adaptive N-body method (1997)
Yu Charlie Hu, Yu Charlie Hu, S. Lennart Johnsson, S. Lennart Johnsson, Shang-hua Teng, Shang-hua Teng
We present a data--parallel formulation of an adaptive version of Anderson's method for N--body particle interactions. Our formulation consists of a storage and computationally efficient...
Optimal Coarsening of Unstructured Meshes (1997)
Gary L. Miller, Dafna Talmor, Shang-Hua Teng
A bounded aspect-ratio coarsening sequence of an unstructured mesh M 0 is a sequence of meshes M 1 ; : : : ; M k such that: ffl M i is a bounded aspect-ratio mesh, and ffl M i is an approximation of...
Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes (1997)
Gary L. Miller, Dafna Talmor, Shang-Hua Teng
A hierarchical gradient of an unstructured mesh M 0 is a sequence of meshes M 1 ; . . . ; M k such that jM k j is smaller than a given threshold mesh size b. The gradient is well-conditioned if for...
Fast Nested Dissection For Finite Element Meshes (1997)
. We present a randomized O(n log log n) time algorithm for constructing a recursive separator decomposition for well-shaped meshes in two and three dimensions. Our algorithm takes O(n log log n)...
How Good is Recursive Bisection? (1997)
Horst D. Simon, Shang-Hua Teng
. The most commonly used p-way partitioning method is recursive bisection (RB). It first divides a graph or a mesh into two equal-sized pieces, by a "good" bisection algorithm, and then...
A Data--Parallel Implementation of the Geometric Partitioning Algorithm (1997)
Yu Charlie, Shang-hua Teng, S. Lennart Johnsson
We present a data-parallel, High Performance Fortran (HPF) implementation of the geometric partitioning algorithm. The geometric partitioning algorithm has provably good partitioning quality. To our...
A Data--Parallel Adaptive (1997)
Body Method, Yu Charlie Hu, S. Lennart Johnsson, Shang-hua Teng
We present a data--parallel formulation of an adaptive version of Anderson's method for N --body particle interactions. Our formulation consists of a storage and computationally efficient...
Well-Spaced Points for Numerical Methods (1997)
Dafna Talmor, Guy Blelloch, Alan M. Frieze, Noel J. Walkington, Shang-hua Teng
mesh generation, mesh coarsening, multigrid Abstract A numerical method for the solution of a partial differential equation (PDE) requires the following steps: (1) discretizing the domain (mesh...
Separators for sphere-packings and nearest neighbor graphs (1997)
Gary L. Miller, Shang-hua Teng, William Thurston, Stephen A. Vavasis
Abstract. A collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. We show that for every k-ply system �, there is a sphere S that...
Spectral partitioning works: planar graphs and finite element meshes (1996)
Daniel A. Spielman, Shang-hua Teng
Spectral partitioning methods use the Fiedler vector---the eigenvector of the secondsmallest eigenvalue of the Laplacian matrix---to find a small separator of a graph. These methods are important...
Spectral partitioning works: planar graphs and finite element meshes (1996)
Daniel A. Spielman, Shang-hua Teng
Spectral partitioning methods use the Fiedler vector---the eigenvector of the second-smallest eigenvalue of the Laplacian matrix---to find a small separator of a graph. These methods are important...
High Performance Fortran for Highly Irregular Problems (1996)
Yu Charlie Hu, S. Lennart Johnsson, Shang-Hua Teng, Y. Charlie, Hu S. Lennart
We present a general data parallel formulation for highly irregular problems in High Performance Fortran (HPF). Our formulation consists of (1) a method for linearizing irregular data structures (2)...
Automated Parallel Solution of Unstructured PDE Problems (1996)
Anja Feldmann, Omar Ghattas, John R. Gilbert, Gary L. Miller, David R. O'hallaron, Eric J. Schwabe, ...
This article describes Archimedes, an automated system for solving partial differential equations on geometrically complex domains using distributed memory supercomputers. The tasks of such a system...
Partitioning Meshes with Lines and Planes (1996)
Feng Cao John, John R. Gilbert, Shang-hua Teng
We investigate several geometric methods for dividing an irregular mesh into pieces of roughly equal size with few interconnecting edges. All these methods are based on cutting a mesh with a line (in...
Automated Parallel Solution of Unstructured PDE Problems (1996)
Anja Feldmann, Omar Ghattas, John R. Gilbert, Gary L. Miller, David R. O'Hallaron, Eric J. Schwabe, ...
This article describes Archimedes, an automated system for solving partial differential equations on geometrically complex domains using distributed memory supercomputers. The tasks of such a system...
Control Volume Meshes using Sphere Packing: Generation, Refinement and Coarsening (1996)
Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington, Han Wang
. In this paper we present a sphere-packing technique for Delaunay-based mesh generation, refinement and coarsening. We have previously established [10] that a bounded radius of ratio of...
Partitioning Meshes with Lines and Planes (1996)
Feng Cao, John R. Gilbert, Shang-Hua Teng
We investigate several geometric methods for dividing an irregular mesh into pieces of roughly equal size with few interconnecting edges. All these methods are based on cutting a mesh with a line (in...
Geometric mesh partitioning: Implementation and experiments (1995)
John R. Gilbert, Gary L. Miller, Shang-hua Teng
We investigate a method of dividing an irregular mesh into equal-sized pieces with few interconnecting edges. The method's novel feature is that it exploits the geometric coordinates of the mesh...
How Good is Recursive Bisection? (1995)
Horst D. Simon, Shang-Hua Teng
. The most commonly used p-way partitioning method is recursive bisection (RB). It first divides a graph or a mesh into two equal sized pieces, by a "good" bisection algorithm, and then...
Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington
We present new geometrical and numerical analysis structure theorems for the Delaunay diagram of point sets in IR d for a fixed d where the point sets arise naturally in numerical methods. In...
Geometric Spectral Partitioning (1995)
Tony F. Chan, John R. Gilbert, Shang-Hua Teng
We investigate a new method for partitioning a graph into two equal-sized pieces with few connecting edges. We combine ideas from two recently suggested partitioning algorithms, spectral bisection...
Generating Local Addresses and Communication Sets for Data-Parallel Programs (1995)
Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Shang-Hua Teng, ...
Generating local addresses and communication sets is an important issue in distributedmemory implementations of data-parallel languages such as High Performance Fortran. We demonstrate a storage...
Moments of Inertia and Graph Separators (1994)
Keith D. Gremban, Gary L. Miller, Shang-Hua Teng
Graphs that arise from the nite element or nite dierence methods often include geometric information such as the coordinates of the nodes of the graph. The geometric separator algorithm of Miller,...
Geometric Spectral Partitioning (1994)
Tony Chan, John R. Gilbert, Shang-hua Teng
We investigate a new method for partitioning a graph into two equal-sized pieces with few connecting edges. We combine ideas from two recently suggested partitioning algorithms, spectral bisection...
Parallel construction of quadtrees and quality triangulations (1993)
We describe efficient PRAM algorithms for constructing unbalanced quadtrees, balanced quadtrees, and quadtree-based finite element meshes. Our algorithms take time O(log n) for point set input and...
Optimal Online Scheduling of Parallel Jobs with Dependencies (1993)
We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific...
Optimal Evaluation of Array Expressions on Massively Parallel Machines (1992)
Siddhartha Chatterjee Research, Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Shang-hua Teng
this article was presented at the Second Workshop on Languages, Compilers, and Runtime Environments for Distributed Memory Multiprocessors, Boulder, Colorado, September 30#October 2, 1992.
"[R]esults of this thesis represent a joint work with Gary Miller and Steven Vavasis. An extended abstract of this joint work will appear in the 32nd Annual Symposium on Foundations of Computer...
Dynamic Scheduling on Parallel Machines (1991)
Anja Feldmann, Jirí Sgall, Shang-Hua Teng
We study the problem of online job-scheduling on parallel machines with different network topologies. An online scheduling algorithm schedules a collection of parallel jobs with known resource...
Point placement for meshless methods using Sphere packing and Advancing Front methods
Xiang-yang Li, Shang-Hua Teng, Alper Üngör, Alper Ungor
es (patches) is defined by the support function and the overlap criteria described above. We prove that biting method can be used to generate a good point set for meshless methods. Introduction...