Network profile

Erel Segal-Halevi

Reputation

1,628

1.6k
1.3k
945

2018
2019
2020
2021

Top tag

ds.algorithms

Next privilege

2,000 Rep.

Edit questions and answers

Badges

Newest

Next badge

0/1

Impact

4 posts edited

0 helpful flags

122 votes cast

23 Questions

Votes Activity Newest Views

votes

answer

views

Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?

cg.comp-geom

Jan 2 '16 at 18:54 Erel Segal-Halevi 1,628

votes

answer

338

views

Partitioning a rectangle without harming inner rectangles

cg.comp-geom

Nov 19 '18 at 0:15 David Eppstein 49.8k

votes

answers

308

views

The complexity of finding a Borsuk-Ulam point

approximation-algorithms time-complexity topology algebraic-topology

Aug 8 '15 at 11:41 usul 6,869

votes

answers

690

views

A partition problem in which some numbers may be cut

np-hardness reductions partition-problem

Oct 21 '19 at 20:03 Erel Segal-Halevi 1,628

votes

answer

304

views

Winning strategy in the game of triplets

gt.game-theory combinatorial-game-theory

Aug 21 '19 at 19:10 Community♦ 1

votes

answer

245

views

A partition problem with order constraints

np-hardness partition-problem

Jul 25 '19 at 7:35 Erel Segal-Halevi 1,628

votes

answers

882

views

Are there problems for which divide-and-conquer / recursion is provably useless?

cc.complexity-theory recursion

Jan 11 '16 at 14:30 Community♦ 1

votes

answers

146

views

What can you do with a moving knife besides cutting a cake?

computability turing-machines machine-models

Apr 2 '15 at 11:00 Erel Segal-Halevi 1,628

votes

answer

138

views

Complexity of approximating a real function using queries

reference-request complexity-classes approximation-algorithms query-complexity computing-over-reals

Jul 20 at 10:30 Aryeh 9,108

votes

answer

316

views

Largest rectangle not touching any rock in a square field

cg.comp-geom

Jan 2 '16 at 23:52 Community♦ 1

votes

answers

187

views

A complexity-class of problems that cannot be solved in finite time

cc.complexity-theory reference-request computing-over-reals

Feb 24 at 17:31 Erel Segal-Halevi 1,628

votes

answer

views

Solving an LP with at most m-1 nonzeros

np-hardness linear-programming

Jan 27 '19 at 6:29 Erel Segal-Halevi 1,628

votes

answers

104

views

Reduction from a geometric decision problem to its maximization problem

cg.comp-geom oracles packing

Jan 1 '14 at 19:16 Erel Segal-Halevi 1,628

votes

answer

144

views

Is set packing easier when the sets are squares?

ds.algorithms packing

Dec 24 '13 at 8:18 Erel Segal-Halevi 1,628

votes

answers

147

views

Minimum relevant variables in linear system - additive approximation

approximation-algorithms optimization linear-programming approximation-hardness

Jan 9 '19 at 20:24 Sasho Nikolov 17.9k

votes

answers

107

views

Partitioning a connected polygon into connected pieces of equal area

cg.comp-geom partition-problem polygon

Feb 24 at 7:55 David Eppstein 49.8k

votes

answer

122

views

Maximum-minimum satisfiability

approximation-algorithms optimization sat

Jan 9 '19 at 20:43 james 36

vote

answer

views

What is the run-time of the bin packing approximation algorithm?

approximation-algorithms time-complexity

Feb 11 at 17:15 Erel Segal-Halevi 1,628

vote

answers

views

Additive welfare maximization under matroid constraints

optimization

Sep 9 at 14:34 Erel Segal-Halevi 1,628

vote

answers

120

views

Enumerate all allocations of points in a simplex

ds.algorithms simplex

Mar 9 '19 at 23:17 D.W. 9,849

votes

answer

136

views

A k-approximation to k-way number partitioning

approximation-algorithms partition-problem

Apr 23 at 14:03 Community♦ 1

votes

answers

136

views

3-partition problem without the restriction to triplets

reductions partition-problem

Oct 28 at 5:58 Erel Segal-Halevi 1,628

-4

votes

answer

111

views

How to say “select the largest” when there can be more than one [closed]

ds.algorithms terminology

Oct 31 '13 at 10:14 David Richerby 2,705

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

23 Questions

Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?

Partitioning a rectangle without harming inner rectangles

The complexity of finding a Borsuk-Ulam point

A partition problem in which some numbers may be cut

Winning strategy in the game of triplets

A partition problem with order constraints

Are there problems for which divide-and-conquer / recursion is provably useless?

What can you do with a moving knife besides cutting a cake?

Complexity of approximating a real function using queries

Largest rectangle not touching any rock in a square field

A complexity-class of problems that cannot be solved in finite time

Solving an LP with at most m-1 nonzeros

Reduction from a geometric decision problem to its maximization problem

Is set packing easier when the sets are squares?

Minimum relevant variables in linear system - additive approximation

Partitioning a connected polygon into connected pieces of equal area

Maximum-minimum satisfiability

What is the run-time of the bin packing approximation algorithm?

Additive welfare maximization under matroid constraints

Enumerate all allocations of points in a simplex

A k-approximation to k-way number partitioning

3-partition problem without the restriction to triplets

How to say “select the largest” when there can be more than one [closed]