110 captures

09 Jan 2000 - 13 Dec 2024

Apr MAY Jun 03

2009 2010 2011

success

fail

About this capture

COLLECTED BY

Organization: Alexa Crawls

Starting in 1996, Alexa Internet has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the Wayback Machine after an embargo period.

Collection: alexa_web_2010

this data is currently not publicly accessible.

TIMESTAMPS

The Wayback Machine - https://web.archive.org/web/20100503065142/http://www.nada.kth.se:80/~viggo/wwwcompendium/node85.html

MAXIMUM CUT

• INSTANCE: Graph $G=\left(V,E\right)$.

• SOLUTION: A partition of V into disjoint sets $V_1$ and $V_2$.

• MEASURE: The cardinality of the cut, i.e., the number of edges with one end point in $V_1$ and one endpoint in $V_2$.

  
  

• Good News: Approximable within 1.1383 [198].

• Bad News: APX-complete [393].

• Comment: Not approximable within 1.0624 [242]. Admits a PTAS if $\vert E\vert =\Theta(\vert V\vert^2)$ [39]. Variation in which the degree of G is bounded by a constant B for $B \ge 3$ is still APX-complete [393] and [9]. Variation in which each edge has a nonnegative weight and the objective is to maximize the total weight of the cut is as hard to approximate as the original problem [128] and admits a PTAS for dense instances [162] and for metric weights [164]. Variation in which some pairs of vertices are restricted to be on the same side (or on different sides) is still approximable within 1.138 [198].

  MAXIMUM BISECTION, the weighted problem with the additional constraint that the partition must cut the graph into halves of the same size, is approximable within 1.431 [472]. Admits a PTAS for some classes of weighted dense instances of MAXIMUM BISECTION [162].

  MINIMUM BISECTION, the problem where the partition must cut the graph into halves of the same size and the number of edges between them is to be minimized, admits a PTAS if the degree of each vertex is $\Theta(\vert V\vert)$ [39].

• Garey and Johnson: ND16