Tag Archives: theory-and-practice-sitting-in-a-tree

Items of some interest:

Posted on by

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

  • Jonathan Lethem’s ‘Neote­nous Aes­thetic” — Mis­ter Bit — Wired​.it

    ‘Dur­ing the brief, but very inter­est­ing Q&A ses­sion, Lethem argued that inter­net cul­ture brought the “closet into the open”, that is, it gave ephemera, triv­i­al­i­ties, and every­day activ­i­ties “A new kind of vis­i­bil­ity”. “Peo­ple have always been pro­duc­ing weird stuff and have always been engag­ing in arcane activ­i­ties,” Lethem remarked. “What is really new is the fact the now we can see it. We can see it all. We can quan­tify what we do — or not do — online.” Lethem men­tioned the uncanny abil­ity to track, in real time, “how many books I am not sell­ing on Ama­zon”. “Real­ity has acquired a new level of mea­sur­a­bil­ity”. “The activ­i­ties we per­form in our dig­i­tal age are not nec­es­sar­ily new. What is new is that. We. Can. See. Them. All.”.’

    one-​​measures-​​a-​​circle inter­per­me­ation access local­ism

  • Sex, Oil, and Video­tape | Mother Jones

    “Loom­ing over Saylor’s con­fronta­tion with Bolen­baugh was the EPA’s Sep­tem­ber 27 cleanup dead­line, and it appears that Enbridge and its con­trac­tors were feel­ing the pres­sure as it drew near. In early Sep­tem­ber, after the Michi­gan Mes­sen­ger pub­lished its exposé on the use of undoc­u­mented work­ers by Hall­mark Indus­trial, another group of work­ers employed by a dif­fer­ent Enbridge con­trac­tor came for­ward with detailed sto­ries of how they had been instructed to con­ceal oil at the same site. Work­ers would land on an island, they said, remove all veg­e­ta­tion, and then lay out absorbent pom-​​poms, all per EPA reg­u­la­tions. But once the top layer of oil was absorbed, they were instructed to rake dirt over the area to make it appear as though it had been dug out. One worker described his super­vi­sor show­ing him the process step-​​by-​​step, con­clud­ing with sprin­kling a thin layer of dirt on top. “He said, ‘There, now they can’t see it. It is clean,’” the worker told the Mes­sen­ger. Another worker described being told to cover pock­ets of oil with leaves and sticks. As a last step, such areas were cor­doned off with cau­tion tape.”

    oil­spill Kala­ma­zoo local whistle­blower

  • [1204.4200] Dis­crete Dynam­i­cal Genetic Pro­gram­ming in XCS

    “A num­ber of rep­re­sen­ta­tion schemes have been pre­sented for use within Learn­ing Clas­si­fier Sys­tems, rang­ing from binary encod­ings to neural net­works. This paper presents results from an inves­ti­ga­tion into using a dis­crete dynam­i­cal sys­tem rep­re­sen­ta­tion within the XCS Learn­ing Clas­si­fier Sys­tem. In par­tic­u­lar, asyn­chro­nous ran­dom Boolean net­works are used to rep­re­sent the tra­di­tional condition-​​action pro­duc­tion sys­tem rules. It is shown pos­si­ble to use self-​​adaptive, open-​​ended evo­lu­tion to design an ensem­ble of such dis­crete dynam­i­cal sys­tems within XCS to solve a num­ber of well-​​known test problems.”

    genetic-​​programming learning-​​classifier-​​systems representation-​​theory design-​​patterns boolean-​​networks nudge-​​targets nice

  • Why Is Darwin’s Tan­gled Bank Tan­gled? : 13.7: Cos­mos And Cul­ture : NPR

    Sad to hear him still phras­ing this sim­ple truth so obscurely: Not “Because, on the scale of mol­e­c­u­lar bind­ing site recog­ni­tion, say a few tens of angstroms in length, height and width and sev­eral other fea­tures such as polar­ity, van-​​der-​​Waal forces, and so on, there are far fewer effec­tively dif­fer­ent mol­e­c­u­lar shapes than there are kinds of mol­e­cules.“ … but “Because there are fewer sto­ries than there are facts.”

    oh-​​stu pragmatism-it-ain’t philosophy-​​of-​​science

  • Math Notes | Futil­ity Closet

    So for finite sequences of dig­its, which sequences are such that the most right-​​truncated sub­strings are prime? Which are such that the most right-​​repeating exten­sions are prime?

    nudge-​​targets number-​​theory indirect-​​link

  • Home — Scal­able and Mod­u­lar Archi­tec­ture for CSS

    “I’ve been ana­lyz­ing my process (and the process of those around me) and fig­ur­ing out how best to struc­ture code for projects on a larger scale. What I’ve found is a process that works equally well for sites small and large. Learn how to struc­ture your CSS to allow for flex­i­bil­ity and main­tain­abil­ity as your project and your team grows.”

    css tuto­r­ial best-​​practices graphic-​​design via-​​trek

  • [1204.3678] Crowd Mem­ory: Learn­ing in the Collective

    “Crowd algo­rithms often assume work­ers are inex­pe­ri­enced and thus fail to adapt as work­ers in the crowd learn a task. These assump­tions fun­da­men­tally limit the types of tasks that sys­tems based on such algo­rithms can han­dle. This paper explores how the crowd learns and remem­bers over time in the con­text of human com­pu­ta­tion, and how more real­is­tic assump­tions of worker expe­ri­ence may be used when design­ing new sys­tems. We first demon­strate that the crowd can recall infor­ma­tion over time and dis­cuss pos­si­ble impli­ca­tions of crowd mem­ory in the design of crowd algo­rithms. We then explore crowd learn­ing dur­ing a con­tin­u­ous con­trol task. Recent sys­tems are able to dis­guise dynamic groups of work­ers as crowd agents to sup­port con­tin­u­ous tasks, but have not yet con­sid­ered how such agents are able to learn over time. We show, using a real-​​time gam­ing set­ting, that crowd agents can learn over time, and ‘remem­ber’ by pass­ing strate­gies from one gen­er­a­tion of work­ers to the next, despite high turnover rates in the work­ers com­pris­ing them. We con­clude with a dis­cus­sion of future research direc­tions for crowd mem­ory and learning.”

    crowd­sourc­ing learn­ing agent-​​based collective-​​intelligence mem­ory nudge-​​targets

  • [0911.1582] Manip­u­lat­ing Tour­na­ments in Cup and Round Robin Competitions

    “In sports com­pe­ti­tions, teams can manip­u­late the result by, for instance, throw­ing games. We show that we can decide how to manip­u­late round robin and cup com­pe­ti­tions, two of the most pop­u­lar types of sport­ing com­pe­ti­tions in poly­no­mial time. In addi­tion, we show that find­ing the min­i­mal num­ber of games that need to be thrown to manip­u­late the result can also be deter­mined in poly­no­mial time. Finally, we show that there are sev­eral dif­fer­ent vari­a­tions of stan­dard cup com­pe­ti­tions where manip­u­la­tion remains polynomial.”

    algo­rithms eco­nom­ics game-​​theory nudge-​​targets

  • Intro­duc­ing the Jour­nal of Dig­i­tal Human­i­ties — ProfHacker — The Chron­i­cle of Higher Education

    “If the con­tents of the inau­gural issue—which range from an essay argu­ing that human­ists need to under­stand and inter­pret quan­ti­ta­tive data to a review of the Word­Seer text analy­sis tool—fall out­side your usual schol­arly domain, then cer­tainly the journal’s edi­to­r­ial and pub­lish­ing appa­ra­tus will piqué your interest. As Dan Cohen explained in a sep­a­rate blog post, the jour­nal oper­ates under the model of catch­ing the good—of find­ing sub­stan­tive and valu­able dig­i­tal human­i­ties work “in what­ever for­mat, and wher­ever, it exists.” Blogs, pod­casts, Twit­ter con­ver­sa­tions, slideshows, and so on, these are all venues in which sig­nif­i­cant and, though I hate to use such an ungainly word, impact­ful work is being done. The reg­u­lar and guest edi­tors “catch” this work, and then pro­vide lay­ers of eval­u­a­tion and review before it appears in JDH.”

    digital-​​humanities jour­nal to-​​read two-​​cultures-​​only-​​one-​​of-​​which-​​can-​​write

  • [1005.4159] The Com­plex­ity of Manip­u­lat­ing $k$-Approval Elections

    “An impor­tant prob­lem in com­pu­ta­tional social choice the­ory is the com­plex­ity of unde­sir­able behav­ior among agents, such as con­trol, manip­u­la­tion, and bribery in elec­tion sys­tems. These kinds of vot­ing strate­gies are often tempt­ing at the indi­vid­ual level but dis­as­trous for the agents as a whole. Cre­at­ing elec­tion sys­tems where the deter­mi­na­tion of such strate­gies is dif­fi­cult is thus an impor­tant goal. …”

    vot­ing game-​​theory design-​​patterns mechanism-​​design nudge-​​targets

  • [0903.1147] Tetravex is NP-​​complete

    “Tetravex is a widely played one per­son com­puter game in which you are given $n^2$ unit tiles, each edge of which is labelled with a num­ber. The objec­tive is to place each tile within a $n$ by $n$ square such that all neigh­bour­ing edges are labelled with an iden­ti­cal num­ber. Unfor­tu­nately, play­ing Tetravex is com­pu­ta­tion­ally hard. More pre­cisely, we prove that decid­ing if there is a tiling of the Tetravex board is NP-​​complete. Decid­ing where to place the tiles is there­fore NP-​​hard. This may help to explain why Tetravex is a good puz­zle. This result com­pli­ments a num­ber of sim­i­lar results for one per­son games involv­ing tiling. For exam­ple, NP-​​completeness results have been shown for: the offline ver­sion of Tetris, KPlumber (which involves rotat­ing tiles con­tain­ing draw­ings of pipes to make a con­nected net­work), and short­est slid­ing puz­zle prob­lems. It raises a num­ber of open ques­tions. For exam­ple, is the infi­nite ver­sion Turing-​​complete? How do we gen­er­ate Tetravex prob­lems which are truly puz­zling as ran­dom NP-​​complete prob­lems are often sur­pris­ing easy to solve? Can we observe phase tran­si­tion behav­iour? What about the com­plex­ity of the prob­lem when it is guar­an­teed to have an unique solu­tion? How do we gen­er­ate puz­zles with unique solutions?”

    mathematical-​​recreations computational-​​complexity algo­rithms nudge-​​targets

  • [1204.4286] Fair Allo­ca­tion With­out Trade

    “We con­sider the age-​​old prob­lem of allo­cat­ing items among dif­fer­ent agents in a way that is effi­cient and fair. Two papers, by Dolev et al. and Ghodsi et al., have recently stud­ied this prob­lem in the con­text of com­puter sys­tems. Both papers had sim­i­lar mod­els for agent pref­er­ences, but advo­cated dif­fer­ent notions of fair­ness. We for­mal­ize both fair­ness notions in eco­nomic terms, extend­ing them to apply to a larger fam­ily of util­i­ties. Not­ing that in set­tings with such util­i­ties effi­ciency is eas­ily achieved in mul­ti­ple ways, we study notions of fair­ness as cri­te­ria for choos­ing between dif­fer­ent effi­cient allo­ca­tions. Our tech­ni­cal results are algo­rithms for find­ing fair allo­ca­tions cor­re­spond­ing to two fair­ness notions: Regard­ing the notion sug­gested by Ghodsi et al., we present a polynomial-​​time algo­rithm that com­putes an allo­ca­tion for a gen­eral class of fair­ness notions, in which their notion is included. For the other, sug­gested by Dolev et al., we show that a com­pet­i­tive mar­ket equi­lib­rium achieves the desired notion of fair­ness, thereby obtain­ing a polynomial-​​time algo­rithm that com­putes such a fair allo­ca­tion and solv­ing the main open prob­lem raised by Dolev et al.”

    eco­nom­ics game-​​theory fair­ness algo­rithms phi­los­o­phy design-​​patterns

  • Why is Esti­mat­ing so Hard? | 8th Light

    “It turns out that we don’t know the pro­ce­dure. We haven’t got any clue to just how dif­fi­cult the pro­ce­dure is. We aren’t com­put­ers. We don’t fol­low pro­ce­dures. And so com­par­ing the com­plex­ity of the man­ual task, to the com­plex­ity of the pro­ce­dure is invalid. This is one of the rea­sons that esti­mates are so hard, and why we get them wrong so often. We look at a task that seems easy and esti­mate it on that basis, only to find that writ­ing down the pro­ce­dure is actu­ally quite intri­cate. We blow the esti­mate because we esti­mate the wrong thing.”

    esti­ma­tion agile-​​practices philosophy-​​of-​​engineering man­age­ment self-​​definition plan­ning

  • [1204.4374] Higher Order City Voronoi Diagrams

    “We inves­ti­gate higher-​​order Voronoi dia­grams in the city met­ric. This met­ric is induced by quick­est paths in the L1 met­ric in the pres­ence of an accel­er­at­ing trans­porta­tion net­work of axis-​​parallel line segments. …”

    computational-​​geometry algo­rithms voronoi-​​diagrams diver­sity network-​​theory nudge-​​targets

  • Topic mod­el­ing made just sim­ple enough. | The Stone and the Shell

    “Com­puter sci­en­tists make LDA seem com­pli­cated because they care about prov­ing that their algo­rithms work. And the proof is indeed brain-​​squashingly hard. But the prac­tice of topic mod­el­ing makes good sense on its own, with­out proof, and does not require you to spend even a sec­ond think­ing about “Dirich­let dis­tri­b­u­tions.” When the math is approached in a prac­ti­cal way, I think human­ists will find it easy, intu­itive, and empow­er­ing. This post focuses on LDA as short­hand for a broader fam­ily of “prob­a­bilis­tic” tech­niques. I’m going to ask how they work, what they’re for, and what their lim­its are.”

    text-​​processing clas­si­fi­ca­tion algo­rithms lovely two-​​cultures-​​only-​​one-​​of-​​which-​​can-​​write

  • Math­e­mati­cians are Giraffe Hunters by Barry Mazur | berfrois

    “No won­der life (i.e., the thing that my once 10-​​year old niece referred to as “the thing that isn’t fair”) comes to us as a fil­i­gree of ash sto­ries. Walk­ing down the street past a cou­ple in con­ver­sa­tion, an over­heard mor­pheme, a mere glance at a wrongly but­toned rain­coat, sparks a nar­ra­tive in our imag­i­na­tion. Ask any ques­tion begin­ning with “why?” and the answer will surely be a story, or it will be embed­ded in a story. Or, at the very least, it will offer a tempt­ing thread for some story that you your­self will hold onto, embell­ish even, as you try to absorb the answer. We inter­po­late between such frag­ments. This is, for many of us, sim­ply the way we think. What about the “why ques­tions” in sci­ence, in logic, in math­e­mat­ics? We should acknowl­edge how they are often “what ques­tions” or “how ques­tions” in dis­guise. Or how they slide down into such ques­tions, as the ever-​​elusive, ever-​​illusory quest for an X that actu­ally causes a Y dis­solves. Some of the more sat­is­fy­ing answers to sci­en­tific “why” ques­tions involves deft rephras­ing. “Why is the sky blue?” is replaced by the ques­tion “what is the func­tion that describes scat­ter­ing ampli­tude as depen­dent on wave-​​length”?”

    math­e­mat­ics philosophy-​​of-​​mathematics sto­ry­telling prag­ma­tism theory-​​and-​​practice-​​sitting-​​in-​​a-​​tree what-​​is-​​it-​​good-​​for-​​hunh

Items of some interest:

Posted on by

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

Items of some interest…

Posted on by

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 17⁄16.”

    graph-​​theory geom­e­try algo­rithms computational-​​geometry nudge-​​targets

Items of some interest…

Posted on by

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

  • Hebrew Typog­ra­phy

    beau­ti­ful lettering

    typog­ra­phy hebrew graphic-​​design cal­lig­ra­phy let­ter­ing

  • [1110.5376] A Quan­ti­ta­tive Test of Pop­u­la­tion Genet­ics Using Spatio-​​Genetic Pat­terns in Bac­te­r­ial Colonies

    “It is widely accepted that pop­u­la­tion genet­ics the­ory is the cor­ner­stone of evo­lu­tion­ary analy­ses. Empir­i­cal tests of the the­ory, how­ever, are chal­leng­ing because of the com­plex rela­tion­ships between space, dis­per­sal, and evo­lu­tion. Crit­i­cally, we lack quan­ti­ta­tive val­i­da­tion of the spa­tial mod­els of pop­u­la­tion genet­ics. Here we com­bine ana­lyt­ics, on and off-​​lattice sim­u­la­tions, and exper­i­ments with bac­te­ria to per­form quan­ti­ta­tive tests of the the­ory. We study two bac­te­r­ial species, the gut microbe Escherichia coli and the oppor­tunis­tic pathogen Pseudomonas aerug­i­nosa, and show that spatio-​​genetic pat­terns in colony biofilms of both species are accu­rately described by an exten­sion of the one-​​dimensional stepping-​​stone model. We use one empir­i­cal mea­sure, genetic diver­sity at the colony periph­ery, to para­me­ter­ize our mod­els and show that we can then accu­rately pre­dict another key vari­able: the degree of short-​​range cell migra­tion along an edge. More­over, the model allows us to esti­mate other key para­me­ters includ­ing effec­tive pop­u­la­tion size (den­sity) at the expan­sion fron­tier. While our exper­i­men­tal sys­tem is a sim­pli­fi­ca­tion of nat­ural micro­bial com­mu­nity, we argue it is a proof of prin­ci­ple that the spa­tial mod­els of pop­u­la­tion genet­ics can quan­ti­ta­tively cap­ture organ­is­mal evolution.”

    bacterial-​​genetics evo­lu­tion micro­bi­ol­ogy exper­i­ment cute

  • NDFD Data­base Contents

    “You can access NDFD ele­ments via file trans­fer pro­to­col (ftp), http, eXten­si­ble Markup Lan­guage (XML), or web browser. Links to the data, sup­port­ing infor­ma­tion and soft­ware are listed below:…”

    weather data raw-​​data-​​now government2.0 nudge-​​targets ref­er­ence fore­casts

  • The Per­for­ma­tiv­ity of Net­works — Kieran Healy

    “The “per­for­ma­tiv­ity the­sis” is the claim that parts of con­tem­po­rary eco­nom­ics and finance, when car­ried out into the world by pro­fes­sion­als and pop­u­lar­iz­ers, refor­mat and reor­ga­nize the phe­nom­ena they pur­port to describe, in ways that bring the world into line with the­ory. Prac­ti­cal tech­nolo­gies, cal­cu­la­tive devices and portable algo­rithms give actors tools to imple­ment par­tic­u­lar mod­els of action. I argue that social net­work analy­sis is per­for­ma­tive in the same sense as the cases stud­ied in this lit­er­a­ture. Social net­work analy­sis and finance the­ory are sim­i­lar in key aspects of their devel­op­ment and effects. For the case of eco­nom­ics, evi­dence for weaker ver­sions of the per­for­ma­tiv­ity the­sis in quite good, and the strong for­mu­la­tion is cir­cum­stan­tially sup­ported. Net­work the­ory eas­ily meets the evi­den­tial thresh­old for the weaker ver­sions; I offer empir­i­cal exam­ples that sup­port the strong (or “Bar­ne­sian”) for­mu­la­tion. Whether these par­al­lels are a mark in favor of the the­sis or a strike against it is an open ques­tion. I argue that the social net­work tech­nolo­gies and mod­els now being “per­formed” build out sys­tems of gen­er­al­ized reci­procity, con­nec­tiv­ity, and commons-​​based pro­duc­tion. This is in con­trast both to an ear­lier net­work imagery that empha­sized self-​​interest and entre­pre­neur­ial exploita­tion of struc­tural oppor­tu­ni­ties, and to the model of action typ­i­cally con­sid­ered to be per­formed by eco­nomic technologies.”

    network-​​theory network-​​culture eco­nom­ics cultural-​​dynamics theory-​​and-​​practice-​​sitting-​​in-​​a-​​tree

Items of some interest…

Posted on by

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

  • A sec­ond front

    “Increas­ingly, this seems to be a war for sur­vival.  I under­stand that tra­di­tional pub­lish­ers are get­ting more and more des­per­ate as the dig­i­tal rev­o­lu­tion pro­ceeds and they con­tinue to dither about how to address it.  But aca­d­e­mic fac­ulty mem­bers are the source of almost all the con­tent these pub­lish­ers pub­lish, so this behav­ior is an extreme exam­ple of bit­ing the hand that feeds them.  It is even more stu­pid, in my opin­ion, than the strat­egy of record­ing indus­try who is suing its own cus­tomers, because these pub­lish­ers are attack­ing a group that is both their cus­tomers and those who sup­ply them with a prod­uct in the first place.”

    copy­right academic-​​culture libraries good-​​eating-​​on-​​one-​​of-​​those disintermediation-​​targets

  • jQuery for Absolute Begin­ners: The Com­plete Series | Nettuts+

    “Hi every­one! Today, I posted the final screen­cast in my “jQuery for Absolute Begin­ners” series on the The­me­For­est Blog. If you’re unfa­mil­iar – over the course of about a month, I posted fif­teen video tuto­ri­als that teach you EXACTLY how to use the jQuery library. We start by down­load­ing the library and even­tu­ally work our way up to cre­at­ing an AJAX style-​​switcher. I’m very proud of this series; pos­si­bly more than any other that I’ve done for Envato.”

    javascript jQuery tuto­r­ial pod­cast video

  • Noodle­soft: Hazel FAQ

    “In gen­eral, Hazel can mon­i­tor any folder but keep in mind that cer­tain fold­ers may not be good can­di­dates. For instance, P2P and other apps that might down­load a file slowly, may have their files moved before they are com­pletely down­loaded. In cases like this, it is best if the pro­gram has an option to down­load to one folder then move them auto­mat­i­cally to another (Trans­mis­sion has such an option). This sec­ond folder is the one you should have Hazel mon­i­tor. Hazel does have spe­cial sup­port for Safari, Camino, Fire­fox, Mail and Speed Down­load and knows how to iden­tify when their down­loads are com­plete. We will be adding sup­port for more apps as time goes on so if you have a favorite app of yours you would like sup­ported, please let us know and we’ll look into adding support.”

    util­i­ties MacOS power-​​user sysad­min

  • Kate Oneal and the Myth­i­cal Ital­ian Restau­rant | xPro​gram​ming​.com

    ‘“The artist sug­gested this: ‘Let’s set a dead­line and total bud­get. I’ll keep you posted on how much is being spent, and of course we’ll have the pic­ture on the wall to look at. By the time we’re about half-​​way through, it should be of high enough qual­ity, and have enough pic­ture ele­ments, that we could stop any time. You’ll have more ideas, of course, but by then we’ll both have a sense of how fast we can progress, and you can choose the most valu­able things to add or change. You’ll have total con­trol over how the pic­ture winds up, and if you want to, we can stop on or before the money runs out.’ “Guido wasn’t entirely con­vinced. He wanted to know how he could be sure he wouldn’t be left with a hor­ri­bly ugly wall. The artist told him that she would guar­an­tee to paint it back over and stop any time he wanted, and said she would start by work­ing in some tem­po­rary pig­ment like chalk, so they could erase and change things easily.’

    project-​​management metaphor agile-​​management

  • Our Waste­ful Health Care Sys­tem — NYTimes​.com

    “The other key thing to pay atten­tion to is who this mar­ket­ing cam­paign was tar­geted at: key deci­sion­mak­ers at providers and insur­ance com­pa­nies. Those are the peo­ple who decide whether med­ical pro­ce­dures get ordered. It’s not patients. Patients aren’t going to expe­ri­ence a loss of free­dom or sat­is­fac­tion because an expert reviewer at the Inde­pen­dant Pay­ment Advi­sory Board makes the call as to whether a pro­ce­dure is med­ically ben­e­fi­cial, rather than the cor­re­spond­ing bureau­crat at their insur­ance provider or at the for-​​profit clinic they’re attending.”

    medical-​​culture cor­po­ratism public-​​policy insur­ance health­care mar­ket­ing

  • The Value of Fol­low­ing Pas­sion in a Job­less World — Lane Wal­lace — Life — The Atlantic

    “If I were a 22-​​year-​​old read­ing all this, the whole notion of adult­hood would seem like a prison sen­tence worth try­ing to avoid. But more impor­tantly, the entire premise upon which all this advice is based is false.  Pas­sion, despite how often we use the term to tout com­pany com­mit­ment or extol roman­tic excite­ment, is often mis­un­der­stood or con­fused with other motivations. Many peo­ple view dreams and pas­sion exactly as Brooks painted it: as a hope­lessly ide­al­is­tic, self­ish, or irre­spon­si­ble choice that is dia­met­ri­cally opposed to com­mit­ment to oth­ers, respon­si­bil­ity, secu­rity, or success. But I have spent the past year and a half research­ing a book about pas­sion and peo­ple who fol­low pas­sion­ate paths in life, and noth­ing I’ve found backs up that premise or belief. Indeed, I would argue that pas­sion is one of the most impor­tant ele­ments in any effort to improve a com­mu­nity, build some­thing of value in the world, and even sur­vive tough times or a daunt­ing econ­omy. The fact that it also tends to lead to a sense of ful­fill­ment within an indi­vid­ual is cer­tainly one of its benefits—but it’s not the dri­ving force that com­pels some­one down the pas­sion road.”

    work­life moti­va­tion David-Brooks-doesn’t-deserve-a-lot-of-respect pas­sion

  • Let It Roll — CFO Mag­a­zine — May 2011 Issue — CFO​.com

    “Sep­a­rat­ing the three deci­sions has enabled the com­pany to set tar­gets that are more ambi­tious, intel­li­gent, and moti­vat­ing, says Bogsnes. As a result, the fore­casts are less biased, and resource allo­ca­tion is more dynamic and self-​​regulating. “The ‘bank’ is open 12 months a year, not just six weeks in the fall,” he says. “By mak­ing resource deci­sions as late as pos­si­ble instead of in an annual bud­get, we have bet­ter infor­ma­tion — not just about project attrac­tive­ness but also about our capac­ity to fund or man new projects.“ Encour­aged by pos­i­tive results from aban­don­ing the bud­get, Sta­toil recently decided to abol­ish the cal­en­dar year as a plan­ning tool and intro­duce a busi­ness– and event-​​driven man­age­ment process in its stead.”

    bud­get­ing finance man­age­ment plan­ning fore­cast­ing agility

  • About That Recipe

    “Inter­preters are cou­plers. They enable the two peo­ple, groups, or cul­tures to under­stand each other because they under­stand both. While the meth­ods men­tioned above can facil­i­tate a fur­ther under­stand­ing of past food cul­tures, what about the other part of the connection—between peo­ple today and in the future? The his­tor­i­cal inter­preter has the unusual task of cou­pling peo­ple in one group about which she can only know a part, one group she knows well, and, if she pub­lishes her inter­pre­ta­tion in any form, one group in the future, about which she can­not know. The ques­tion is, then, not only what can we learn about mean­ings in the past, but how can we inter­pret those mean­ings to peo­ple today and in the future?”

    quotable his­tory

  • Lan­guage Log » Straw men and Bee Science

    “Let me start by say­ing that there’s a way to take all this that makes it entirely cor­rect. The key motive of sci­ence is expla­na­tion, and it’s often essen­tial to abstract away from the com­plex­i­ties of raw obser­va­tion, and so on. I took courses from Chom­sky as an under­grad­u­ate and a grad­u­ate stu­dent, and I’m grate­ful for what I learned from him, and for the emi­nently fair way that he always treated me. But increas­ingly, it seems to me, he has been ele­vat­ing his per­sonal dis­taste for the com­plex­i­ties of the real world into a sys­tem­atic phi­los­o­phy. To the extent that oth­ers accept these views, it excludes them from par­tic­i­pa­tion in (what I think are) the most promis­ing and excit­ing cur­rent direc­tions in the sci­ences of speech and language.”

    Noam-​​Chomsky theory-​​and-​​practice-​​sitting-​​in-​​a-​​tree bias sci­ence learning-​​from-​​data

  • Bozo Sapi­ens: Robert Owen: Laboriousness

    “Owen had neglected to notice that expec­ta­tions also change through cir­cum­stance. As our com­mu­nal con­di­tions advance, we all tend to want to become the prophet, not merely the con­gre­ga­tion. Once the prob­lem of sur­vival is solved, it’s no longer enough not to be starv­ing or abused or over­worked – we want per­sonal sat­is­fac­tion and self-​​direction. So, yes: some of the great names in busi­ness – the Low­ell mills, Hershey’s, Cadbury’s, Lever Broth­ers, Google – applied dilute Owenism to great effect, but suc­cess makes employ­ees become more indi­vid­u­al­ist and ask for more of their reward in cash, while hard times make share­hold­ers less gen­er­ous, point­ing out that plenty of peo­ple would take the job with­out the crêche, lec­ture series, or com­pany brass band. Shift­ing expec­ta­tion dri­ves the carousel for another turn; we remain ambiva­lent about work, this thing we do through most of our wak­ing lives, because we still don’t know what it is for.”

    institutional-​​design col­lab­o­ra­tion workantile-​​exchange diver­sity plan-​​for-​​change

  • Cal­cu­lated Risk: The Excess Vacant Hous­ing Supply

    “It is no sur­prise that Florida has the largest num­ber of excess vacant units and that Nevada has the largest per­cent­age of excess vacant units. What might be a sur­prise to some is that Cal­i­for­nia is below the U.S. average.”

    financial-​​crisis real-​​estate housing-​​bubble public-​​policy

  • Strin­gent Response: Sys­tems biol­ogy approach to strin­gent response

    “All this results in bac­te­ria gam­bling all the time: some react to stim­u­lus, some don’t, some pro­duce more pro­teins in response to it, some less. This leads to so called phe­no­typic het­ero­gene­ity, when oth­er­wise (genet­i­cally) iden­ti­cal bac­te­ria become very dif­fer­ent in terms of their responses. This could be a good thing and also could be a bad thing. Hav­ing a col­lec­tion of dif­fer­ent bugs instead of a clone army will pro­vide cer­tain ver­sa­til­ity: some are ready for one con­di­tions, and some are ready for oth­ers. For instance, some are ready to grow and divide right away and some are slower and more cau­tious. Both types of cells can be ben­e­fi­cial in dif­fer­ent con­di­tions: the active ones will drive the pop­u­la­tion growth, but will be sen­si­tive to the antibi­otic treat­ment, and the pas­sive ones will wait until the treat­ment is over and then they will come to life. Sounds like a good strat­egy (and it has a name, this strat­egy — “bed hedg­ing”) and I guess it is exactly the rea­son why clone armies never caught on.”

    diver­sity systems-​​biology evolutionary-​​biology game-​​theory emergent-​​design

  • Time as a Com­pet­i­tive Advan­tage | Mike Cohn’s Blog — Suc­ceed­ing With Agile®

    “Inno­va­tion has become a fer­tile area in which com­pa­nies seek com­pet­i­tive advan­tage today. This has served Apple well over the past decade. I don’t think inno­v­a­tive­ness will be going away soon as a source of com­pet­i­tive advan­tage. But I do won­der whether time is run­ning out on time as a com­pet­i­tive advan­tage. If agile and other inno­va­tions lead us to a world where all com­pa­nies can deliver new prod­ucts and ser­vices equally quickly, com­pa­nies will need to find newer ways to dif­fer­en­ti­ate themselves.”

    inno­va­tion com­pet­i­tive­ness agility strat­egy

  • See­ing Things On Mars: A Long His­tory of Mar­t­ian Illu­sions and Human Delu­sions |Parei­do­lia & Opti­cal Illu­sions | Space​.com

    “Humans have been see­ing strange things on the sur­face of Mars for cen­turies. From the 1700s up through the present day, wide­spread fame has been avail­able to any­one able to pro­duce even the slight­est bit of flimsy evi­dence that there’s Mar­t­ian life.”

    nanohis­tory Mars psy­choce­ram­ics astron­omy belief optical-​​illusions

  • The rise of Glen­core, the biggest com­pany you’ve never heard of | Busi­ness | The Guardian

    “But so jeal­ously has Glasen­berg guarded his pri­vacy that his name means noth­ing to the man on the street. For years he has avoided speeches and, until recently, had given only one inter­view – to his old uni­ver­sity mag­a­zine. If you live out­side the world of com­modi­ties trad­ing or cor­po­rate finance, Ivan Glasen­berg is prob­a­bly the Most Impor­tant Busi­ness­man You Have Never Heard Of.”

    glob­al­iza­tion finance cor­po­ra­tions pri­vacy transparency-it-ain’t

  • Datameer snags $9.25M more to ana­lyze mas­sive amounts of data | VentureBeat

    “Datameer, a com­pany that allows users to ana­lyze mas­sive amounts of data with­out tech­ni­cal know-​​how, today announced a sec­ond round of fund­ing for $9.25 mil­lion. The money will be used to hire addi­tional employ­ees for its engi­neer­ing, sales, and mar­ket­ing teams.”

    data-​​analysis data-​​mining star­tups fund­ing bub­b­li­cious

  • Plan Would Force U. of Wis­con­sin to Return $39-​​Million in U.S. Broad­band Grants — Wired Cam­pus — The Chron­i­cle of Higher Education

    “Another pro­vi­sion in the plan would bar any Uni­ver­sity of Wis­con­sin cam­pus from par­tic­i­pat­ing in advanced net­works con­nect­ing research insti­tu­tions world­wide, accord­ing to Mr. Evers’s memo. For exam­ple, the Madi­son cam­pus would have to with­draw from Internet2, a high-​​speed net­work­ing con­sor­tium, said Mr. Giroux.”

    pol­i­tics Wis­con­sin stu­pid­ity broad­band telecom­mu­ni­ca­tions cor­po­ratism