Erel Segal-Halevi

GitHub
erelsgl.github.io
Israel
Member for 9 years, 4 months

Reputation

1,640

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

128 votes cast

25 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,640

votes

answer

339

views

Partitioning a rectangle without harming inner rectangles

cg.comp-geom

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

votes

answers

314

views

The complexity of finding a Borsuk-Ulam point

approximation-algorithms time-complexity topology algebraic-topology

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

votes

answers

730

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,640

votes

answer

306

views

Winning strategy in the game of triplets

gt.game-theory combinatorial-game-theory

Aug 21 '19 at 19:10 CommunityBot 1

votes

answer

258

views

A partition problem with order constraints

np-hardness partition-problem

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

votes

answers

894

views

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

cc.complexity-theory recursion

Jan 11 '16 at 14:30 CommunityBot 1

votes

answers

147

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,640

votes

answer

142

views

Complexity of approximating a real function using queries

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

Jul 20 '20 at 10:30 Aryeh 9,652

votes

answer

317

views

Largest rectangle not touching any rock in a square field

cg.comp-geom

Jan 2 '16 at 23:52 CommunityBot 1

votes

answers

189

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,640

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,640

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,640

votes

answer

145

views

Is set packing easier when the sets are squares?

ds.algorithms packing

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

votes

answers

153

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

120

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.9k

votes

answer

123

views

Maximum-minimum satisfiability

approximation-algorithms optimization sat

Jan 9 '19 at 20:43 james 36

vote

answer

121

views

The "electricity packing" problem

reference-request scheduling packing

Jun 27 at 21:02 Chandra Chekuri 6,365

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,640

vote

answers

views

Additive welfare maximization under matroid constraints

optimization

Sep 9 '20 at 14:34 Erel Segal-Halevi 1,640

vote

answers

122

views

Enumerate all allocations of points in a simplex

ds.algorithms simplex

Mar 9 '19 at 23:17 D.W. 10.1k

votes

answer

148

views

A k-approximation to k-way number partitioning

approximation-algorithms partition-problem

Aug 21 at 14:07 CommunityBot 1

votes

answers

views

Using bin-packing algorithms to approximate maximum-makespan

approximation-algorithms optimization partition-problem scheduling packing

Aug 18 at 11:33 Erel Segal-Halevi 1,640

votes

answers

155

views

3-partition problem without the restriction to triplets

reductions partition-problem

Oct 28 '20 at 5:58 Erel Segal-Halevi 1,640

-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,715

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

25 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

The "electricity packing" problem

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

Using bin-packing algorithms to approximate maximum-makespan

3-partition problem without the restriction to triplets

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