Profile Activity

Austin Buchanan

Meta user

Network profile

Reputation

1,611

1.6k
1.5k
1.5k

2016
2017
2018
2019

Top tag

cc.complexity-theory

Next privilege

2,000 Rep.

Edit questions and answers

Badges

Newest

Pundit

Next badge

0/1

Impact

4 posts edited

5 helpful flags

529 votes cast

Summary Answers Questions Tags Badges Favorites Bounties Reputation All actions

14 Questions

Views Newest Activity Votes

votes

answers

views

Reasons to believe $P \ne NP \cap coNP$ (or not)

cc.complexity-theory np conditional-results

Sep 12 '14 at 15:31 Community♦ 1

votes

answer

views

How can a problem be in NP, be NP-hard and not NP-complete?

cc.complexity-theory np-hardness complexity-classes terminology

Apr 13 '13 at 19:03 Community♦ 1

votes

answers

576

views

Exact exponential-time algorithms for 0-1 programming

np-hardness integer-programming exp-time-algorithms

Aug 29 '13 at 23:47 Community♦ 1

votes

answer

198

views

When does a graph admit an orientation in which there is at most one s-t walk?

graph-theory directed-acyclic-graph

May 7 '15 at 23:34 David Eppstein 45.5k

votes

answers

373

views

Exact exponential-time algorithms for 0-1 programs with nonnegative data

np-hardness integer-programming exp-time-algorithms

Dec 16 '13 at 22:06 Community♦ 1

votes

answer

641

views

Max-weight connected subgraph problem in planar graphs

reference-request np-hardness reductions planar-graphs

Mar 22 '14 at 21:03 Marzio De Biasi 18.9k

votes

answers

views

Hardest problems to approximate

approximation-hardness clique

Jun 12 '13 at 8:19 Mohammad Al-Turkistany 13.9k

votes

answers

451

views

Weighted vertex-connectivity; global min vertex-cut

graph-algorithms max-flow-min-cut

Jun 6 '13 at 23:46 Austin Buchanan 1,611

votes

answers

101

views

Testbed of perfect graphs

perfect-graph

Dec 5 '13 at 12:05 Austin Buchanan 1,611

votes

answer

185

views

When are all facets rank facets? (for independence system polyhedra)

independence polytope

Aug 12 '15 at 15:06 Yohann 36

votes

answer

186

views

What is known about this binary representation polytope?

linear-programming integer-programming polytope

May 30 '14 at 14:04 Sasho Nikolov 16.7k

votes

answers

282

views

Approximation factor when objective can be negative

approximation-algorithms

May 21 '13 at 4:34 Austin Buchanan 1,611

votes

answer

168

views

Dual/complement of independence system

co.combinatorics independence set-system

Jun 28 '13 at 4:14 Sasho Nikolov 16.7k

vote

answer

206

views

Node-weighted steiner problem with few terminals

graph-algorithms np-hardness parameterized-complexity fixed-parameter-tractable

Jul 25 '14 at 15:30 david 877

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

14 Questions

Reasons to believe $P \ne NP \cap coNP$ (or not)

How can a problem be in NP, be NP-hard and not NP-complete?

Exact exponential-time algorithms for 0-1 programming

When does a graph admit an orientation in which there is at most one s-t walk?

Exact exponential-time algorithms for 0-1 programs with nonnegative data

Max-weight connected subgraph problem in planar graphs

Hardest problems to approximate

Weighted vertex-connectivity; global min vertex-cut

Testbed of perfect graphs

When are all facets rank facets? (for independence system polyhedra)

What is known about this binary representation polytope?

Approximation factor when objective can be negative

Dual/complement of independence system

Node-weighted steiner problem with few terminals