John's user avatar
John's user avatar
John's user avatar
John
  • Member for 1 year, 8 months
  • Last seen more than a week ago
4 votes
0 answers
71 views

distinguishments between query complexity of membership oracles and standard time complexity

3 votes
0 answers
97 views

maximum independent set in graphs with small number of edges

3 votes
1 answer
175 views

Hardness of Maximum Independent Set in 3-Colorable Graphs

2 votes
0 answers
58 views

Is Finding an *Unbalanced* Biclique in Bipartite Graphs Hard?

2 votes
1 answer
73 views

Set Cover with Multiple covers

2 votes
0 answers
26 views

Hardness of 3-Partition with Small Target Value

1 vote
0 answers
36 views

Hardness of Coloring based on a Black-Box Hardness of Independent Set

1 vote
0 answers
66 views

Unbounded Knapsack Instance with a Single Optimum that takes each Item Once?

1 vote
0 answers
278 views

Does the Minimum Spanning Tree (MST) problem become NP-hard when adding edge profits?

1 vote
1 answer
175 views

3 Matroid Intersection, a Special Case

0 votes
0 answers
90 views

When Exponential Costs are Essential for NP-Hardness?

0 votes
0 answers
70 views

Is this Knapsack/Subset Sum Variant NP-Hard?

0 votes
1 answer
65 views

Is this edge-partitioning NP-Hard?

0 votes
1 answer
68 views

Solving non-linear programming with large number of variables

0 votes
0 answers
45 views

What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?

0 votes
0 answers
113 views

Can one obtain an FPTAS for Knapsack by Rounding Weights (and not Profits)?