Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up

Here's how it works:

Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore Our Questions

active hot week month

more tags

votes

answers

views

Approximate answer to Max-SMT (bitvector) query

approximation-algorithms sat max2sat

asked Aug 3 at 21:56 lightning 260

votes

answers

109

views

Max cut problem between two connected subgraphs

cc.complexity-theory reference-request graph-algorithms approximation-algorithms randomized-algorithms

modified Jul 27 at 8:58 Saeed 2,730

votes

answer

views

Complexity of distributively verifying that the diameter is small

cc.complexity-theory ds.algorithms graph-algorithms approximation-algorithms dc.distributed-comp

answered Jun 20 at 18:06 R B 6,259

votes

answers

views

What is the best approximation and exact algorithm for vertex cover on cubic graphs?

cc.complexity-theory ds.algorithms np-hardness complexity-classes approximation-algorithms

asked Jun 19 at 8:32 Dabbler 6

vote

answers

views

maximization of non-negative monotone supermodular set function with cardinality constraints

reference-request approximation-algorithms optimization submodularity

asked Jun 18 at 10:27 user49739 6

vote

answers

views

k-center 2.0: A stronger k-center condition

graph-theory graph-algorithms approximation-algorithms clustering

asked Jun 15 at 15:15 Karagounis Z 4

votes

answers

views

Smoothed analysis to compare algorithms

ds.algorithms approximation-algorithms smoothed-analysis

asked May 23 at 9:47 Andrius Vaicenavicius 31

votes

answer

views

How can algorithms with nested combinatorial searches be quasi-linear?

ds.algorithms approximation-algorithms

answered May 16 at 7:57 Peter Taylor 1,141

votes

answers

views

Is there a sensible notion of an approximation algorithm for an undecidable problem?

computability approximation-algorithms parameterized-complexity halting-problem

answered May 15 at 15:13 Ted 184

votes

answers

639

views

Edge and vertex fault tolerance in graphs

graph-theory graph-algorithms np-hardness approximation-algorithms

modified May 8 at 7:26 Iehab Kamiel 1

votes

answers

223

views

W[1]-hard problems with FPT time approximation algorithms

ds.algorithms approximation-algorithms parameterized-complexity fixed-parameter-tractable

answered May 1 at 22:12 Chandra Chekuri 5,248

votes

answers

views

Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)?

approximation-algorithms online-algorithms

asked Apr 26 at 20:22 PattaraS 11

votes

answers

views

Metric 1-Center in l-infinity norm (when dimension is part of the input)

cc.complexity-theory ds.algorithms np-hardness approximation-algorithms cg.comp-geom

modified Apr 13 at 5:12 D.W. 7,025

vote

answer

views

Does the following 2-rounds distributed algorithm approximates a maximal matching well?

ds.algorithms approximation-algorithms randomized-algorithms dc.distributed-comp matching

modified Apr 10 at 15:42 Neal Young 4,030

Browse More Questions

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore Our Questions

Approximate answer to Max-SMT (bitvector) query

Max cut problem between two connected subgraphs

Complexity of distributively verifying that the diameter is small

What is the best approximation and exact algorithm for vertex cover on cubic graphs?

maximization of non-negative monotone supermodular set function with cardinality constraints

k-center 2.0: A stronger k-center condition

Smoothed analysis to compare algorithms

How can algorithms with nested combinatorial searches be quasi-linear?

Is there a sensible notion of an approximation algorithm for an undecidable problem?

Edge and vertex fault tolerance in graphs

W[1]-hard problems with FPT time approximation algorithms

Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)?

Metric 1-Center in l-infinity norm (when dimension is part of the input)

Does the following 2-rounds distributed algorithm approximates a maximal matching well?

Hot Network Questions