These are my recent Pin​board​.in links:

• [1109.5664] Deter­min­is­tic Fea­ture Selec­tion for $k$-means Clustering

  “We study fea­ture selec­tion for $k$-means clus­ter­ing. Although the lit­er­a­ture con­tains many meth­ods with good empir­i­cal per­for­mance, algo­rithms with prov­able the­o­ret­i­cal behav­ior have only recently been devel­oped. Unfor­tu­nately, these algo­rithms are ran­dom­ized and fail with, say, a con­stant prob­a­bil­ity. We address this issue by pre­sent­ing a emph{deterministic} fea­ture selec­tion algo­rithm for $k$-means with the­o­ret­i­cal guar­an­tees. At the heart of our algo­rithm lies a deter­min­is­tic method for decom­po­si­tions of the identity.”
  
  clus­ter­ing sta­tis­tics algo­rithms nudge-​​targets

• [1110.5190] Constant-​​factor approx­i­ma­tion of dom­i­na­tion num­ber in sparse graphs

  “The k-​​domination num­ber of a graph is the min­i­mum size of a set X such that every ver­tex of G is in dis­tance at most k from X. We give a lin­ear time constant-​​factor approx­i­ma­tion algo­rithm for k-​​domination num­ber in classes of graphs with bounded expan­sion, which include e.g. proper minor-​​closed graph classes, classes closed on topo­log­i­cal minors or classes of graphs that can be drawn on a fixed sur­face with bounded num­ber of cross­ings on each edge. The algo­rithm is based on the fol­low­ing approx­i­mate min-​​max char­ac­ter­i­za­tion. A sub­set A of ver­tices of a graph G is d-​​independent if the dis­tance between each pair of ver­tices in A is greater than d. Note that the size of the largest 2k-​​independent set is a lower bound for the k-​​domination num­ber. We show that every graph from a fixed class with bounded expan­sion con­tains a 2k-​​independent set A and a k-​​dominating set D such that |D|=O(|A|), and these sets can be found in lin­ear time. For dom­i­na­tion num­ber (k=1) the assump­tions can be relaxed, and the result holds for all graph classes with arrange­abil­ity bounded by a constant.”
  
  operations-​​research com­bi­na­torics graph-​​theory algo­rithms nudge-​​targets

• [1112.1945] Approx­i­ma­tion Algo­rithms for Edge Par­ti­tioned Ver­tex Cover Problems

  “In the Par­tial Ver­tex Cover (PVC) prob­lem we are given an undi­rected graph G = (V, E), a pos­i­tive cost asso­ci­ated with each ver­tex and a pos­i­tive inte­ger k and the goal is to find a min­i­mum cost sub­set of ver­tices S such that atleast k edges of the graph are cov­ered. In this paper we con­sider two new gen­er­al­iza­tion of the PVC prob­lem. In the first vari­a­tion which we call Par­ti­tion Ver­tex Cover (Partition-​​VC) prob­lem, the edges of the graph G are divided into n dis­joint par­ti­tions $P_​1, P_​2… P_​n$ and we have to select a min­i­mum cost sub­set of ver­tices S such that atleast $k_​i$ edges are cov­ered from par­ti­tion $P_​i$. In the sec­ond vari­a­tion which we call Knap­sack Par­ti­tion Ver­tex Cover (KPVC) prob­lem, in addi­tion to the pre­vi­ous con­di­tions, each edge e has a profit $pi_{e}$ asso­ci­ated with it and we have an added knap­sack con­straint that the total profit of the cov­ered edges in par­ti­tion $P_​i$ should be atleast $Pi_​i$. We give an $O(log n)$ approx­i­ma­tion for both the prob­lems using a com­bi­na­tion of deter­min­is­tic round­ing and ran­dom­ized round­ing approach that oper­ates on the LP strength­ened by adding Knap­sack Cover inequal­i­ties as pro­posed by Carr, Fleis­cher, Leung & Phillips. We also show that these bounds can not be fur­ther improved by reduc­ing the set cover prob­lem to the Partition-​​VC prob­lem in poly­no­mial time. We also give an $O(f)$ approx­i­ma­tion for the Partition-​​VC prob­lem using a pri­mal dual schema where f is the max­i­mum num­ber of edges in any partition.”
  
  operations-​​research graph-​​theory graph-​​partitioning linear-​​programming nudge-​​targets

• [1101.3501] Con­ver­gence rates of effi­cient global opti­miza­tion algorithms

  “Effi­cient global opti­miza­tion is the prob­lem of min­i­miz­ing an unknown func­tion f, using as few eval­u­a­tions f(x) as pos­si­ble. It can be con­sid­ered as a continuum-​​armed ban­dit prob­lem, with noise­less data and sim­ple regret. Expected improve­ment is per­haps the most pop­u­lar method for solv­ing this prob­lem; the algo­rithm per­forms well in exper­i­ments, but lit­tle is known about its the­o­ret­i­cal prop­er­ties. Imple­ment­ing expected improve­ment requires a choice of Gauss­ian process prior, which deter­mines an asso­ci­ated space of func­tions, its reproducing-​​kernel Hilbert space (RKHS). When the prior is fixed, expected improve­ment is known to con­verge on the min­i­mum of any func­tion in the RKHS. We begin by pro­vid­ing con­ver­gence rates for this pro­ce­dure. The rates are opti­mal for func­tions of low smooth­ness, and we mod­ify the algo­rithm to attain opti­mal rates for smoother func­tions. For prac­ti­tion­ers, how­ever, these results are some­what mis­lead­ing. Pri­ors are typ­i­cally not held fixed, but depend on para­me­ters esti­mated from the data. For stan­dard esti­ma­tors, we show this pro­ce­dure may never dis­cover the min­i­mum of f. We then pro­pose alter­na­tive esti­ma­tors, cho­sen to min­i­mize the con­stants in the rate of con­ver­gence, and show these esti­ma­tors retain the con­ver­gence rates of a fixed prior.”
  
  opti­miza­tion operations-​​research theory-​​and-​​practice-​​sitting-​​in-​​a-​​tree nudge-​​targets algo­rithms

• [1011.1939] Dis­crete Par­ti­tion­ing and Cov­er­age Con­trol for Gos­sip­ing Robots

  “We pro­pose dis­trib­uted algo­rithms to auto­mat­i­cally deploy a team of mobile robots to par­ti­tion and pro­vide cov­er­age of a non-​​convex envi­ron­ment. To han­dle arbi­trary non-​​convex envi­ron­ments, we rep­re­sent them as graphs. Our par­ti­tion­ing and cov­er­age algo­rithm requires only short-​​range, unre­li­able pair­wise “gos­sip” com­mu­ni­ca­tion. The algo­rithm has two com­po­nents: (1) a motion pro­to­col to ensure that neigh­bor­ing robots com­mu­ni­cate at least spo­rad­i­cally, and (2) a pair­wise par­ti­tion­ing rule to update ter­ri­tory own­er­ship when two robots com­mu­ni­cate. By study­ing an appro­pri­ate dynam­i­cal sys­tem on the space of par­ti­tions of the graph ver­tices, we prove that ter­ri­tory own­er­ship con­verges to a pairwise-​​optimal par­ti­tion in finite time. This new equi­lib­rium set rep­re­sents improved per­for­mance over com­mon Lloyd-​​type algo­rithms. Addi­tion­ally, we detail how our algo­rithm scales well for large teams in large envi­ron­ments and how the com­pu­ta­tion can run in any­time with lim­ited resources. Finally, we report on large-​​scale sim­u­la­tions in com­plex envi­ron­ments and hard­ware exper­i­ments using the Player/​Stage robot con­trol system.”
  
  com­plex­ol­ogy robot­ics agent-​​based computational-​​geometry nudge-​​targets voronoi emergent-​​design

• [1112.1841] Con­sis­tency of mul­ti­di­men­sional com­bi­na­to­r­ial substitutions

  “Mul­ti­di­men­sional com­bi­na­to­r­ial sub­sti­tu­tions are rules that replace sym­bols by finite pat­terns of sym­bols in Z^d. We focus on the case where the pat­terns are not nec­es­sar­ily rec­tan­gu­lar, which requires a spe­cific descrip­tion of the way they are glued together in the image by a sub­sti­tu­tion. Two prob­lems can arise when defin­ing a sub­sti­tu­tion in such a way: it can fail to be con­sis­tent, and the pat­terns in an image by the sub­sti­tu­tion might over­lap. We prove that it is unde­cid­able whether a two-​​dimensional sub­sti­tu­tion is con­sis­tent or over­lap­ping, and we pro­vide prac­ti­cal algo­rithms to decide these prop­er­ties in some par­tic­u­lar cases.”
  
  frac­tals rewriting-​​systems mathematical-​​recreations amus­ing nudge-​​targets unde­cod­abil­ity

• [1112.3523] Approx­i­mat­ing the Edge Length of 2-​​Edge Con­nected Pla­nar Geo­met­ric Graphs on a Set of Points

  “Given a set $P$ of $n$ points in the plane, we solve the prob­lems of con­struct­ing a geo­met­ric pla­nar graph span­ning $P$ 1) of min­i­mum degree 2, and 2) which is 2-​​edge con­nected, respec­tively, and has max edge length bounded by a fac­tor of 2 times the opti­mal; we also show that the fac­tor 2 is best pos­si­ble given appro­pri­ate con­nec­tiv­ity con­di­tions on the set $P$, respec­tively. First, we con­struct in $O(nlog{n})$ time a geo­met­ric pla­nar graph of min­i­mum degree 2 and max edge length bounded by 2 times the opti­mal. This is then used to con­struct in $O(nlog n)$ time a 2-​​edge con­nected geo­met­ric pla­nar graph span­ning $P$ with max edge length bounded by $sqrt{5}$ times the opti­mal, assum­ing that the set $P$ forms a con­nected Unit Disk Graph. Sec­ond, we prove that 2 times the opti­mal is always suf­fi­cient if the set of points forms a 2 edge con­nected Unit Disk Graph and give an algo­rithm that runs in $O(n^2)$ time. We also show that for $k in O(sqrt{n})$, there exists a set $P$ of $n$ points in the plane such that even though the Unit Disk Graph span­ning $P$ is $k$-vertex con­nected, there is no 2-​​edge con­nected geo­met­ric pla­nar graph span­ning $P$ even if the length of its edges is allowed to be up to ¹⁷⁄₁₆.”
  
  graph-​​theory geom­e­try algo­rithms computational-​​geometry nudge-​​targets