optimization   65648

« earlier    

[1705.04587] Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
We study the Parallel Task Scheduling problem Pm|sizej|Cmax with a constant number of machines. This problem is known to be strongly NP-complete for each m≥5, while it is solvable in pseudo-polynomial time for each m≤3. We give a positive answer to the long-standing open question whether this problem is strongly NP-complete for m=4. As a second result, we improve the lower bound of 1211 for approximating pseudo-polynomial Strip Packing to 54. Since the best known approximation algorithm for this problem has a ratio of 43+ε, this result narrows the gap between approximation ratio and inapproximability result by a significant step. Both results are proven by a reduction from the strongly NP-complete problem 3-Partition.
operations-research  optimization  computational-complexity  benchmarking  approximation  rather-interesting  nudge-targets  consider:approximation 
2 days ago by Vaguery
[1512.03421] The extended 1-perfect trades in small hypercubes
An extended 1-perfect trade is a pair (T0,T1) of two disjoint binary distance-4 even-weight codes such that the set of words at distance 1 from T0 coincides with the set of words at distance 1 from T1. Such trade is called primary if any pair of proper subsets of T0 and T1 is not a trade. Using a computer-aided approach, we classify nonequivalent primary extended 1-perfect trades of length 10, constant-weight extended 1-perfect trades of length 12, and Steiner trades derived from them. In particular, all Steiner trades with parameters (5,6,12) are classified.
combinatorics  to-understand  graph-theory  strings  optimization  constraint-satisfaction  looking-to-see  nudge-targets  consider:looking-to-see  consider:classification  consider:feature-discovery 
2 days ago by Vaguery
[math/0103224] On the Minimum Ropelength of Knots and Links
The ropelength of a knot is the quotient of its length and its thickness, the radius of the largest embedded normal tube around the knot. We prove existence and regularity for ropelength minimizers in any knot or link type; these are C1,1 curves, but need not be smoother. We improve the lower bound for the ropelength of a nontrivial knot, and establish new ropelength bounds for small knots and links, including some which are sharp.
knot-theory  optimization  rather-interesting  feature-construction  geometry  engineering-design  nudge-targets  consider:approximation 
3 days ago by Vaguery

« earlier    

related tags

a  aa  ab  agriculture  analytics  android  ao  apk  app  application  approximation  arel  art  article  arxiv  association  associations  autograd  automation  axiom  ba  benchmarking  bestpractices  bigo  blogging  book  browser  c++  c  cache  clean  code  codepens  combinatorics  compiler  compilers  compression  computational-complexity  consider:approximation  consider:classification  consider:feature-discovery  consider:looking-to-see  constraint-satisfaction  content  coralgables  create  css  data-science  database  deep-learning  design  development  drf  eagerloading  ebook  engineering-design  engineering  entwicklung  example  fast  feature-construction  fl  florida  following  frontend-dev  frontend  garbagecollection  geometry  go  goo  google  gradle  graph-theory  graphql  guide  hosting  html  hyperparameter  image  images  improve  in  includes  increase  information-retrieval  interpreter  ip  javascript  jpg  js  json  kaggle  keywords  knot-theory  landing  learning  libraries  library  linearprogramming  logo  looking-to-see  mac  machine-learning  macos  mail.app  mail  management  marketing  marketingtips  math  mathematics  memory  miami  miamibeach  mind:  mobile  mvt  n+1  nudge-targets  numericalcomputing  numericalmethods  online  opcache  operations-research  optimisation  optimize  organization  orms  page  performance  photography  php  png  postgres  prefetch  preload  presto  production  profiling  programming  pulp  python-numba  python  rails  rather-interesting  react  reference  responsive.design  responsive_images  ror  ruby  rubyonrails  rule  rust  sas  search  searchengine  seo  siteperformance  sitespeed  sketch  slow  smm  socialmedia  software  sp  speed  sql  stream  strings  svg  teamwork  time  timing  tip  tips  to-understand  tool  tools  transpiler  try  tsp  unicode  unix  ux  vfx  walkforward  web.design  web  webdesign  webdev  website  with  wordpress  wp  yoast   

Copy this bookmark:



description:


tags: