Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active Hot Week Month

0

votes

0

answers

41

views

Is p-dimensional matching with (p−1)n edges NP-hard? What about 3n edges?

np-hardness matching

asked Jul 29 at 14:59 Ernie Vigelan 1

4

votes

0

answers

101

views

An NP-hard Hidden Subgroup Problem

cc.complexity-theory np-hardness hiddensubgroupproblem

modified Jul 28 at 7:02 Shaull 4,805

3

votes

1

answer

183

views

$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

np-hardness approximation-algorithms packing extremal-combinatorics chernoff-bound

modified Jul 22 at 1:00 Community♦ 1

2

votes

1

answer

139

views

Coloring intersection graph of squares

graph-theory graph-algorithms np-hardness graph-colouring interval-graphs

modified Jul 14 at 10:24 Saeed 3,410

-2

votes

0

answers

38

views

How hard is this special 3-partition problem?

np-hardness co.combinatorics np-complete proofs partition-problem

asked Jul 10 at 6:39 Rise of Kingdom 53

1

vote

0

answers

39

views

Modifying sets to minimize the distance among each pair of the mean value of sets

np-hardness approximation-algorithms optimization

modified Jul 7 at 2:49 Refrain 45

10

votes

1

answer

292

views

Recent progress on the next-to-shortest-path problem for directed graphs?

np-hardness shortest-path

modified Jul 3 at 15:03 Community♦ 1

6

votes

1

answer

270

views

Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries

cc.complexity-theory np-hardness co.combinatorics optimization

modified Jun 28 at 8:19 Rodrigo de Azevedo 227

-2

votes

1

answer

49

views

Is time-slot matchmaking NP-hard?

cc.complexity-theory np-hardness scheduling

answered Jun 23 at 18:04 user1543037 116

16

votes

0

answers

429

views

a geometric variant of k-medians. NP-hard or in P?

np-hardness polynomial-time set-cover clustering dynamic-programming

modified Jun 17 at 2:04 Neal Young 6,972

1

vote

0

answers

137

views

Triangle detection hardness in regular graphs

ds.algorithms np-hardness lower-bounds

modified Jun 9 at 5:20 domotorp 13.2k

3

votes

0

answers

128

views

Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

np-hardness approximation-hardness coding-theory promise-problems

modified May 23 at 3:09 Root 395

3

votes

1

answer

337

views

How hard is this combinatorial optimisation problem?

ds.algorithms np-hardness co.combinatorics integer-programming proofs

modified May 21 at 8:41 Mikhail Rudoy 2,708

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled