61
61

Sep 23, 2013
09/13

by
Xi Chen; Decheng Dai; Ye Du; Shang-Hua Teng

texts

#
eye 61

#
favorite 0

#
comment 0

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 proof shows that this market-equilibrium problem does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time.

Source: http://arxiv.org/abs/0904.0644v1

83
83

Sep 18, 2013
09/13

by
Nikolaos Laoutaris; Laura J. Poplawski; Rajmohan Rajaraman; Ravi Sundaram; Shang-Hua Teng

texts

#
eye 83

#
favorite 0

#
comment 0

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 has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the...

Source: http://arxiv.org/abs/0806.1727v1

45
45

Sep 18, 2013
09/13

by
Maria-Florina Balcan; Christian Borgs; Mark Braverman; Jennifer Chayes; Shang-Hua Teng

texts

#
eye 45

#
favorite 0

#
comment 0

A central problem in e-commerce is determining overlapping communities among individuals or objects in the absence of external identification or tagging. We address this problem by introducing a framework that captures the notion of communities or clusters determined by the relative affinities among their members. To this end we define what we call an affinity system, which is a set of elements, each with a vector characterizing its preference for all other elements in the set. We define a...

Source: http://arxiv.org/abs/1201.4899v2

25
25

Jun 28, 2018
06/18

by
Yu Cheng; Ho Yee Cheung; Shaddin Dughmi; Ehsan Emamjomeh-Zadeh; Li Han; Shang-Hua Teng

texts

#
eye 25

#
favorite 0

#
comment 0

We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function $g$ from the $n$-dimensional hypercube to the bounded interval $[-1,1]$, and an $n \times m$ matrix $A$ with bounded entries, maximize $g(Ax)$ over $x$ in the $m$-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents...

Topics: Computing Research Repository, Data Structures and Algorithms, Computer Science and Game Theory

Source: http://arxiv.org/abs/1508.03679

52
52

Sep 22, 2013
09/13

by
Konstantin Voevodski; Maria-Florina Balcan; Heiko Roglin; Shang-Hua Teng; Yu Xia

texts

#
eye 52

#
favorite 0

#
comment 0

We study the problem of efficiently clustering protein sequences in a limited information setting. We assume that we do not know the distances between the sequences in advance, and must query them during the execution of the algorithm. Our goal is to find an accurate clustering using few queries. We model the problem as a point set $S$ with an unknown metric $d$ on $S$, and assume that we have access to \emph{one versus all} distance queries that given a point $s \in S$ return the distances...

Source: http://arxiv.org/abs/1101.3620v2

101
101

Sep 22, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 101

#
favorite 0

#
comment 0

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 $\xxt$ within relative distance $\epsilon$ of the solution to $A \xx = \bb$ in time $O (m^{1.31} \log (n \kappa_{f} (A)/\epsilon)^{O (1)})$, where $\kappa_{f} (A)$ is the log of the ratio of the largest to smallest non-zero eigenvalue of $A$. In particular, $\log (\kappa_{f} (A)) = O (b \log n)$, where...

Source: http://arxiv.org/abs/cs/0310036v2

44
44

Sep 23, 2013
09/13

by
Michael Elkin; Yuval Emek; Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 44

#
favorite 0

#
comment 0

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).

Source: http://arxiv.org/abs/cs/0411064v5

52
52

Sep 22, 2013
09/13

by
Kyle Burke; Shang-Hua Teng

texts

#
eye 52

#
favorite 0

#
comment 0

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. Second, like many other interesting games such as Hex and Geography, we prove that deciding whether one can win our game is a PSPACE-complete problem. Third, there is an elegant balance in the game such that neither the first nor the second player always has a decisive advantage. We provide a web-based...

Source: http://arxiv.org/abs/cs/0702153v1

49
49

Sep 18, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 49

#
favorite 0

#
comment 0

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 clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a non-empty local cluster, is nearly linear in the size of the cluster...

Source: http://arxiv.org/abs/0809.3232v1

71
71

Sep 18, 2013
09/13

by
Xi Chen; Xiaotie Deng; Shang-Hua Teng

texts

#
eye 71

#
favorite 0

#
comment 0

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 Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. This is the first of a series of results concerning the complexity of Nash equilibria. In particular, we prove the following theorems: Bimatrix does not have a fully polynomial-time approximation scheme unless every...

Source: http://arxiv.org/abs/0704.1678v1

4
4.0

Jun 30, 2018
06/18

by
Christian Borgs; Jennifer Chayes; Adrian Marple; Shang-Hua Teng

texts

#
eye 4

#
favorite 0

#
comment 0

We provide the first social choice theory approach to the question of what constitutes a community in a social network. Inspired by the classic preferences models in social choice theory, we start from an abstract social network framework, called preference networks; these consist of a finite set of members where each member has a total-ranking preference of all members in the set. Within this framework, we develop two complementary approaches to axiomatically study the formation and structures...

Topics: Computational Complexity, Computer Science and Game Theory, Computing Research Repository, Data...

Source: http://arxiv.org/abs/1410.5152

51
51

Sep 22, 2013
09/13

by
Arvind Sankar; Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 51

#
favorite 0

#
comment 0

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 that $A$ has large growth factor under Gaussian elimination without pivoting. By combining these results, we bound the smoothed precision needed by Gaussian elimination without pivoting. Our results improve the average-case analysis of Gaussian elimination without pivoting performed by Yeung and Chan...

Source: http://arxiv.org/abs/cs/0310022v4

71
71

Sep 18, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 71

#
favorite 0

#
comment 0

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 through the traditional worst-case and average-case analyses. In this talk, we survey some of the smoothed analyses that have been performed.

Source: http://arxiv.org/abs/math/0212413v1

75
75

Sep 18, 2013
09/13

by
Rumi Ghosh; Kristina Lerman; Tawan Surachawala; Konstantin Voevodski; Shang-Hua Teng

texts

#
eye 75

#
favorite 0

#
comment 0

The random walk is fundamental to modeling dynamic processes on networks. Metrics based on the random walk have been used in many applications from image processing to Web page ranking. However, how appropriate are random walks to modeling and analyzing social networks? We argue that unlike a random walk, which conserves the quantity diffusing on a network, many interesting social phenomena, such as the spread of information or disease on a social network, are fundamentally non-conservative....

Source: http://arxiv.org/abs/1102.4639v3

138
138

Sep 17, 2013
09/13

by
Dan A. Spielman; Shang-hua Teng; Alper Ungor

texts

#
eye 138

#
favorite 0

#
comment 0

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 a set of ``independent'' points to insert into the domain, and then update the Delaunay triangulation. We show that such a set of independent points can be constructed efficiently in parallel and that the number of iterations needed is $O(\log^2(L/s))$, where $L$ is the diameter of the domain, and...

Source: http://arxiv.org/abs/cs/0207063v1

48
48

Sep 20, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 48

#
favorite 0

#
comment 0

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 and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma))$. In contrast, the best known bound on the worst-case complexity of linear programming is $O (m^{3} L)$, where $L$ could be as large as $m$. We include an introduction to...

Source: http://arxiv.org/abs/cs/0301019v1

79
79

Sep 23, 2013
09/13

by
Christian Borgs; Michael Brautbar; Jennifer Chayes; Shang-Hua Teng

texts

#
eye 79

#
favorite 0

#
comment 0

A fundamental problem arising in many applications in Web science and social network analysis is, given an arbitrary approximation factor $c>1$, to output a set $S$ of nodes that with high probability contains all nodes of PageRank at least $\Delta$, and no node of PageRank smaller than $\Delta/c$. We call this problem {\sc SignificantPageRanks}. We develop a nearly optimal, local algorithm for the problem with runtime complexity $\tilde{O}(n/\Delta)$ on networks with $n$ nodes. We show that...

Source: http://arxiv.org/abs/1202.2771v5

3
3.0

Jun 30, 2018
06/18

by
Rumi Ghosh; Kristina Lerman; Shang-Hua Teng; Xiaoran Yan

texts

#
eye 3

#
favorite 0

#
comment 0

We study the interplay between a dynamic process and the structure of the network on which it is defined. Specifically, we examine the impact of this interaction on the quality-measure of network clusters and node centrality. This enables us to effectively identify network communities and important nodes participating in the dynamics. As the first step towards this objective, we introduce an umbrella framework for defining and characterizing an ensemble of dynamic processes on a network. This...

Topics: Physics, Discrete Mathematics, Computing Research Repository, Physics and Society, Social and...

Source: http://arxiv.org/abs/1406.3387

69
69

Sep 18, 2013
09/13

by
Michael A. Bender; Bradley C. Kuszmaul; Shang-Hua Teng; Kebin Wang

texts

#
eye 69

#
favorite 0

#
comment 0

A mesh is a graph that divides physical space into regularly-shaped regions. Meshes computations form the basis of many applications, e.g. finite-element methods, image rendering, and collision detection. In one important mesh primitive, called a mesh update, each mesh vertex stores a value and repeatedly updates this value based on the values stored in all neighboring vertices. The performance of a mesh update depends on the layout of the mesh in memory. This paper shows how to find a memory...

Source: http://arxiv.org/abs/0705.1033v2

39
39

Sep 19, 2013
09/13

by
Paul Christiano; Jonathan A. Kelner; Aleksander Madry; Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 39

#
favorite 0

#
comment 0

We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges,...

Source: http://arxiv.org/abs/1010.2921v2

19
19

Jun 30, 2018
06/18

by
Dehua Cheng; Yu Cheng; Yan Liu; Richard Peng; Shang-Hua Teng

texts

#
eye 19

#
favorite 0

#
comment 0

Motivated by a sampling problem basic to computational statistical inference, we develop a nearly optimal algorithm for a fundamental problem in spectral graph theory and numerical analysis. Given an $n\times n$ SDDM matrix ${\bf \mathbf{M}}$, and a constant $-1 \leq p \leq 1$, our algorithm gives efficient access to a sparse $n\times n$ linear operator $\tilde{\mathbf{C}}$ such that $${\mathbf{M}}^{p} \approx \tilde{\mathbf{C}} \tilde{\mathbf{C}}^\top.$$ The solution is based on factoring...

Topics: Computation, Statistics, Mathematics, Computing Research Repository, Numerical Analysis, Data...

Source: http://arxiv.org/abs/1410.5392

6
6.0

Jun 29, 2018
06/18

by
Kristina Lerman; Shang-Hua Teng; Xiaoran Yan

texts

#
eye 6

#
favorite 0

#
comment 0

It is common for people to access multiple social networks, for example, using phone, email, and social media. Together, the multi-layer social interactions form a "integrated social network." How can we extend well developed knowledge about single-layer networks, including vertex centrality and community structure, to such heterogeneous structures? In this paper, we approach these challenges by proposing a principled framework of network composition based on a unified dynamical...

Topics: Physics and Society, Physics, Computing Research Repository, Social and Information Networks

Source: http://arxiv.org/abs/1609.01641

58
58

Sep 21, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 58

#
favorite 0

#
comment 0

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 that of the original. This is equivalent to saying that the Laplacian of the sparsifier is a good preconditioner for the Laplacian of the original. We prove that every graph has a spectral sparsifier of nearly linear size. Moreover, we present an algorithm that produces spectral sparsifiers in time...

Source: http://arxiv.org/abs/0808.4134v3

20
20

Aug 11, 2020
08/20

by
Konstantin Voevodski; Maria-Florina Balcan; Heiko Rglin; Shang-Hua Teng; Yu Xia

data

#
eye 20

#
favorite 0

#
comment 0

Source: http://academictorrents.com/details/9dd1a91e17e2294624f643e3f1073cb26aa39a2c

46
46

Sep 22, 2013
09/13

by
Laura J. Poplawski; Rajmohan Rajaraman; Ravi Sundaram; Shang-Hua Teng

texts

#
eye 46

#
favorite 0

#
comment 0

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. BGP is the glue that holds the Internet together and hence its stability, i.e. the equilibria of fractional BGP games (Haxell, Wilfong), is a matter of practical importance. BBC games (Laoutaris et al) follow in the tradition of the large body of work on network formation games and capture a variety...

Source: http://arxiv.org/abs/0812.0598v2

68
68

Sep 21, 2013
09/13

by
Xi Chen; Xiaotie Deng; Shang-Hua Teng

texts

#
eye 68

#
favorite 0

#
comment 0

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 \epsilon-approximate Nash equilibrium of an n by nbimatrix game, unless PPAD is in P. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional cube with a constant side-length, such as on an n-dimensional cube with side-length 7, and show that they are...

Source: http://arxiv.org/abs/cs/0602043v2

78
78

Sep 21, 2013
09/13

by
Li-Sha Huang; Shang-Hua Teng

texts

#
eye 78

#
favorite 0

#
comment 0

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 Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange problem does not have a fully polynomial-time approximation scheme, that is, there is no algorithm that can compute an \epsilon-approximate market equilibrium in...

Source: http://arxiv.org/abs/cs/0602090v1

57
57

Sep 19, 2013
09/13

by
Nikolaos Laoutaris; Rajmohan Rajaraman; Ravi Sundaram; Shang-Hua Teng

texts

#
eye 57

#
favorite 0

#
comment 0

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 $k$ on the out-degree of each node, and a weight $w_{vu}$ for each ordered pair $(v,u)$ representing the traffic rate from node $v$ to node $u$. Each node $v$ uses up to $k$ directed links to connect to other nodes with an objective to minimize its average distance, using weights $w_{vu}$, to all...

Source: http://arxiv.org/abs/cs/0701071v2

46
46

Sep 20, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 46

#
favorite 0

#
comment 0

We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b, produces a y such that $\norm{y - \pinv{A} b}_{A} \leq \epsilon \norm{\pinv{A} b}_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon)),$ for some constant c. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive...

Source: http://arxiv.org/abs/cs/0607105v5

81
81

Sep 19, 2013
09/13

by
John Dunagan; Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 81

#
favorite 0

#
comment 0

We show that the smoothed complexity of the logarithm of Renegar's condition number is O(log (n/sigma)).

Source: http://arxiv.org/abs/cs/0302011v2

44
44

Sep 19, 2013
09/13

by
Konstantin Voevodski; Maria-Florina Balcan; Heiko Roglin; Shang-Hua Teng; Yu Xia

texts

#
eye 44

#
favorite 0

#
comment 0

Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s in S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. Our algorithm uses an...

Source: http://arxiv.org/abs/1009.5168v2

47
47

Sep 22, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 47

#
favorite 0

#
comment 0

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 performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.

Source: http://arxiv.org/abs/cs/0111050v7

66
66

Sep 21, 2013
09/13

by
Jonathan A. Kelner; James R. Lee; Gregory N. Price; Shang-Hua Teng

texts

#
eye 66

#
favorite 0

#
comment 0

We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate "Riemannian" metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs. In particular, we use our method to show that for any positive integer k, the kth smallest...

Source: http://arxiv.org/abs/1008.3594v3

136
136

Sep 23, 2013
09/13

by
Shiva Kintali; Laura J. Poplawski; Rajmohan Rajaraman; Ravi Sundaram; Shang-Hua Teng

texts

#
eye 136

#
favorite 0

#
comment 0

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 domains of practical significance: Fractional Stable Paths Problem (FSPP) [21] - Internet routing; Core of Balanced Games [41] - Economics and Game theory; Scarf's Lemma [41] - Combinatorics; Hypergraph Matching [1]- Social Choice and Preference Systems; Fractional Bounded Budget Connection Games...

Source: http://arxiv.org/abs/0904.1435v1

38
38

Sep 22, 2013
09/13

by
Xi Chen; Shang-Hua Teng

texts

#
eye 38

#
favorite 0

#
comment 0

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 open whether randomization helps fixed-point computation. Inspired by this open problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a...

Source: http://arxiv.org/abs/cs/0702088v1

4
4.0

Jun 29, 2018
06/18

by
Wei Chen; Shang-Hua Teng

texts

#
eye 4

#
favorite 0

#
comment 0

We study network centrality based on dynamic influence propagation models in social networks. To illustrate our integrated mathematical-algorithmic approach for understanding the fundamental interplay between dynamic influence processes and static network structures, we focus on two basic centrality measures: (a) Single Node Influence (SNI) centrality, which measures each node's significance by its influence spread; and (b) Shapley Centrality, which uses the Shapley value of the influence...

Topics: Physics and Society, Physics, Computing Research Repository, Social and Information Networks

Source: http://arxiv.org/abs/1602.03780

51
51

Sep 19, 2013
09/13

by
Xi Chen; Shang-Hua Teng

texts

#
eye 51

#
favorite 0

#
comment 0

In this paper, inspired by the work of Megiddo on the formation of preferences and strategic analysis, we consider an early market model studied in the field of economic theory, in which each trader's utility may be influenced by the bundles of goods obtained by her social neighbors. The goal of this paper is to understand and characterize the impact of social influence on the complexity of computing and approximating market equilibria. We present complexity-theoretic and algorithmic results...

Source: http://arxiv.org/abs/1009.0309v1

18
18

Jun 26, 2018
06/18

by
Dehua Cheng; Yu Cheng; Yan Liu; Richard Peng; Shang-Hua Teng

texts

#
eye 18

#
favorite 0

#
comment 0

We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_\alpha(G)=D-\sum_{r=1}^d\alpha_rD(D^{-1}A)^r$$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $\alpha=(\alpha_1...\alpha_d)$ are nonnegative coefficients with $\sum_{r=1}^d\alpha_r=1$. Recall that $D^{-1}A$ is the transition matrix of random walks on the graph. The sparsification of...

Topics: Statistics, Discrete Mathematics, Computing Research Repository, Learning, Data Structures and...

Source: http://arxiv.org/abs/1502.03496

59
59

Sep 22, 2013
09/13

by
Adam Tauman Kalai; Shang-Hua Teng

texts

#
eye 59

#
favorite 0

#
comment 0

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 polynomial-time algorithm is known for learning polynomial-sized decision trees (even trees of any super-constant size), even when examples are assumed to be drawn from the uniform distribution on {0,1}^n. We give an algorithm that learns arbitrary polynomial-sized decision trees for {\em most product...

Source: http://arxiv.org/abs/0812.0933v1

48
48

Sep 18, 2013
09/13

by
Nina Amenta; Marshall Bern; David Eppstein; Shang-Hua Teng

texts

#
eye 48

#
favorite 0

#
comment 0

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 arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression...

Source: http://arxiv.org/abs/cs/9809037v2