From 965b5c2121de6b37e236bd57481c90c39fc47fb3 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Tue, 9 Jul 2013 18:54:44 +0200 Subject: Add notes on non-homotropic (and python code) --- notes-on-non-homotropic.pdf | 248 ++++++++++++++++++++++++++++++++++++++++++++ plot.py | 36 ++----- 2 files changed, 255 insertions(+), 29 deletions(-) create mode 100644 notes-on-non-homotropic.pdf diff --git a/notes-on-non-homotropic.pdf b/notes-on-non-homotropic.pdf new file mode 100644 index 0000000..7c450db --- /dev/null +++ b/notes-on-non-homotropic.pdf @@ -0,0 +1,248 @@ +%PDF-1.7 +4 0 obj +<< +/Type /Page +/Resources +<< +/XObject +<< /PAGE0001 7 0 R >> +/ProcSet 6 0 R +>> +/MediaBox [ 0 0 831 584] +/Parent 3 0 R +/Contents 5 0 R +>> +endobj +5 0 obj +<< +/Length 39 +>> +stream +q +831.4 0 0 584.6 0 0 cm +/PAGE0001 Do +Q +endstream +endobj +6 0 obj +[/PDF /ImageB] +endobj +7 0 obj +<< +/Type /XObject +/Subtype /Image +/Name /Page0001 +/Width 3464 +/Height 2436 +/BitsPerComponent 1 +/ColorSpace /DeviceGray +/Filter /CCITTFaxDecode +/DecodeParms +<< +/K -1 /Columns 3464 /Rows 2436 +>> +/Length 43101 +>> +stream +bE +faƔ#$G2: |,$*D%{GZSdr$)MD5 &e6E#LmS P_8lF$JmE(uepܦJ#o&n1$Hմln$~ GL7|5 Zi:^ZThaDu 0KtKVA¦*m+J&E6I5KujYkR4#:Y AV>)HM I %,H\THtBU B"!=%eSi Nbvfen=~)d#8f$+L6M')iN+խ5N:aoMM頊[V]d4L+a zl$GW\%pe +. 2$GИP A$LÔ5H C!HF# (tJ+~[zdQ+DpD|jBA ykPHDhb#[mzݺ z lӽva;tG$_#+0]AB +ϵPDuA#F0rP +*A";6!¬RE9V鈅 ^L >Gv+@U-e%p$(p}"<!p\Cc# PEGH|tGEHA,1eBHRA.X!EN$V I @#7@8&AB# +DD%Dt!h4oM!@ L! 6 i +A4Өoݤ OOS7DGT!'B:#. MU\莈$I#1nZe\GFfM$ AL Tm<4EQ  HH QM#+T.FЈA2 9 4G""!ʌ68 B ABq`ďTFH=! 3B2\!.F,ި$*F 0$BiG0I ôDeHMa">-7ZjhK@#..:.| xCB t $#:#(P"= $#$ID##i I!#H".e7 +ɼAIa A`ξAPݜTDP!ieR菉DL2 $tt0Ik +GH"b#-$GDu ʂ֔>-ҶB5#wMHV.v>Du .BҮ0-',)E7YWiHtHCr|%:n7iR0[ lazCDe3EDu,]ش#5K8S B.-{ ,=&leQPj[bGqC 8eYR(rOS0\I\7B#8rf2ER#FG3C$"ՄG.!E[T4##$ ">GDt Dxմ",gcա 0 j8##C""GEP)`.؈(h)gTEҤʠLi $p\dmA#n)&SMA'Qʋ Ӥ!8(rI(tӱaM$i65l":}1tD|0r:mLppm("I =; I&j0Ҧƽ=]m6Qmܳ"T۫y =G(pV֡$6!uV۰$5݇m-1E:άR.]\&껊i$0iG +GD|M6iU%/BgĻQ$]5@f- A+EuvCiA2 {h,E"GA"B 5E ,2,'J]mb YGlX.Vхdc"75@HE)4x!&PE\DEaԁADE$")B/="++GA1-"UA𡸆Q? CDtlnb2 +Y+VH5Pe=Z $}w;RB.NJ"-I:fsR "0me6HWp̀!!g ^8D!0J.Aˠ@ ]A8ѐ#Sq@a2?́0 <9CDUҶ +*F0/LDDM":KABt(paF#I@&(pl7HZ#-4GBt BA""k$a ڴڄӽ7+ZhGIi#M(pKtBH6Б՗̆A +IT,)r`OL"NL*HE>GI +vm+p}l4 ibLaѐ#GDmL0eJn#D5i؜Dt + ;z\"?l\ D}FtGI"ժtʑZ=]CI*菂@`I$""Dy;VIեm6P8!A)IP@AI eHMB[ TطMH3i$# $6G[t#VH +zA ""Ůݦ$vGFE|AM"8A"Bۆ6g&Ɛi"pm4HFXt)H0bHN &pE:IN: P{*X*fTȏAh*caGRiiDt0&{(p":2w,9caeJ-n V}GtH'qm, +5QTBDu9fG7t`Dua 0AtG +nGMI#m":MI%E TUDGEp"D2t#-&"M L &6f2:IAЅE;H#T$P丌dt]5Am]nB&JpbF莢HD-شWw;eU-RcbGWA4N l Bvd#ҊSA +H7!` R@$]M=mJ.@e^Yau<#ə IH˟Utb"n +#)SM$H>9ܧ;'vGMP莮2"!## FtA@A$A& ^ ѴDy,RB"""۴A&)<8|DuAC6Z%2w>[A \؄/<.Xa)4i \DvT2MN1ՔU 4 $PgnDt$$E^ 0I:.TEA6WnJB)[ :H4\P*I6 t$tGnuH$ a(G! :TA6I"?hDzXn8g"L A E::qa$TlDyJT +Du4Q)\$"* , 9R%g٩*@M&gSD}>$p0@$A'Uyga @Ad"H2bB/tA *A]$#$BC  2:r2'GL v1FGTvC\"bGFXc &"PB8$ >%tDr6@ 'ۦCM\E~FtoH +҄A $!@NҢ>kEeEDtGDtv#r7&ĸ@}]"@9 B9J5CH#(ܹPDN&EmmA $Gu":.G2<a6G7IXB!4+"@u&GDtG@!I"X!4 vh@46,2:LT#$GV6"EI;XAFYAA$pIGJ)&H Pф#!  e@cQ +ȄdkZV":/VnQ!٤ +(("?in U$T+nt#ioI1mR!m4ڄM+T'L4 YkxZ.EW8#/:THK:LB\]M̐A4g9X$'ErH7ItG `*Mi a#kb[Be.z#!A0m$dtD#"6HvI#RlE$eIeVFI[ ++VjDuP=_OT)gXɹ#$:ۦ5nY|D$I +GdxHXM#auQA$BG1#awEA  ":#:&PG@ :nY AA"""""""&P"a-5T+ 9F#.[rl&PXTO\0('N*ک$5i"tGV{ҠI" A FtGUJƲlTL +) Dݶ2IB")=?lj| !J{uv&IAgoE.omz\6" ФVTj%6] `A^H Re) A$BAH B7BۖȎ.$tGZ[I$쎨AKo@HD IIDlLXAuiQn2 D3(AzlEKx": +šaH] aYJZЃFeD!^3ȵ4!HDCB ] B1"e0tGDuHB"PnGn $I$$wHS*BpB|HD#w#+\G4GDt!M+l]$G5 # \wX+a M S?f@t}H$H$8$A& !J.h 0T6  DDH^&lH0nI:.DtB!1; FhDY!a79Z%Ae# a0򖉤C<i$a"tP 0BDdH*Bm4_AZ@*J#x@ 9V +) #ûE AHm -91 HMFT9A C,`fˇDDE:SB)IaHm [B"YRXG.l88iW-0FtB"UHæ*2@B"{vm^õI֡M6nL! ^Q-ݑՋ 5l,f-ӆT.1n*0.6ԷHb#">HBаÆp@$$I$vGyS-dtn "!;#:.A2/I:&R"m">#H!=8 I;vi莈莂$ 'b",㶑QCDH!:#@dPӠ&peB"[Duv;R tmwtGLnpvA۪Z,h!#]D}F$&ӣ"]_0AJҴL2#:igB- F $FiM m#ȵh=E/ Q0EM2(pNTl [DtPPR:l >XuDtLJM؅l0eCEYVk$9G( 4J[m_HC]]DuoR:W)HhDQXT$#Z ]%I$"GDtGP?M +}6dU*$I("="?MN +DXB[B i5ZI:.%&MgT,9fQ4-D"7n8We/5MT@ mݠ";@8Bb &sH2=$GEtGHB)5z1rNQrDm& Ür]Y҈$#AL*+ vy>`# #ΰ<tGPm+Gdr#:P ] <$tA4;l68A"CB$xPB-$@EA0I(AU2vGTHej;SA-Ђ̎I@(t#Bݪ*ۦp$t-DumDEAPogp6);ЈPm mVZz":M&&0l-GB"4,9$wMq d"v[e$ bGXsTEhTjAg,!#ͥbM&Vaʔv4Ct" Ga*;m)qg-PH#! H.a+(7tt@H$]&$##6 (t -7@B⠪ʄsU6uK9ja b%"(^5b%E6AZNl0#,Ih >bG02!MVKA8{GFxzGFa6$,uX8bB .Dx D} &KtH$ 0HڶAGJN#B"s" -YHT ՔHPb)EC `4:+DB[0iq`a$ Q* (ИIl+f0XIRtf̋y0)p@Ђ hH&dbl#@o@Tݢ@A#i$]qli4FDцfA4?!D"hm#.!=": 3 j"#J!g낖r6GBϲX8|;9%z0-AU}BR 4ėA(#l+ РFԴ* ;tn! \4u ! 8A:m"::ukAB"WHfD9 SGvGHAV=@FC .(lNGe%ŋADS+E=z UH#ANNX#$Wʭ+#!I I%lOv(!b莂*tD*2VetGDr>I"ۂMIta8 )&U@B)8aGT|!ӆEӤD|$ "D|D45H":H!P,a5iR0;Dt!E#. acuA!  Ia"R$4R.Za mt9eDy#[DxbBGE]A1Z c#"\$Ct RSaDtfI%Ct$CEqct7NöY1$B"AP}6&PCaD} [D}*P $# E$* " fVAI!p7P$6)&ЂM:b"[BeIa6H8EHWT0M<مByB0I +{ ZAU[GHn+BPa& D}8El0"F-P OM! C>j9&!:MVoӚ]!JؤXvAU(0aM\6IV[ov%t'H0zz;Aeۤm{bIޑ( CS$GNt-ƣntt.qT]Z.>Sfi>Tex$[{ՆaCðm riyD B&A@a mb"4&o&h#mѽӶj#$VmvstGI#s+jl84G#\c p@.2>N6/& V_#t!-I GJl(A dv'#H36(VPmJ A$tAђU %Qv b".#/`A)XRC+d;TLDt )@ +A4#.i!@VcGB$~""!ՈD}$EiuQ`Gy+ŲuDM44Ể(pv +:n4زۋVl+?_OoVAU_Rm%H[ ^RWܠ,4܎$im[=dWV[CmPqhl0Eh[DKj}5N:V6vXթnHI]ն\I4Aŵ[" I$]NfE + vjLs8DERi+JQGšAnݵXH"ûH 쯪PۦH0gU.I"DE菛OPt. @0ՆB[p3@A|"REGM6 AQ0v/L4܏I^MJ.T$iRj,Nz 6$yADH菑YQ}oa]Zh"C({(p~&ʄGilP`$ƭv#ᴘB5J! ZZeVԟ*k ww":hdt]dqH-`(w +6ClAӑդ) H"nڤi NˠECt$+@eI+bF& aM[#b*FA3X hD$#Xv v, &D$"",z 3_ ">!aW S#벶Zz$bAh4G@ N SĎ H AHN"<,m&AIA "! 8IgQ: AnmRIdF($Ӥ X"4jhAI"bH4}4׶F4SGTMilH.C ! Y٪ 6n ]萈8"<;ԋ:$hH!T/N]&tjMġL0֊Z#A^bF[HGMH&xIDy*\ h֭A] ض"2Tv-i +,DtڸeB ! i$tH#-*i5tHA(ra>V- HQVAV/AHupeTl)Q]ӰT,;!#;inLB ȣ[J)gCXUpLö T7nQ#GMA4I7ߥG$6"%樎i;jjH7hS#0{–YqDvm&(!%:2Y0GDt#UR5aDx V "<"HHGVH_kh#q$ a ""R :̹08#hA .z8EX!Ml$$2<}ABtHD2K atG26|DFҶP" EH[@e9Pm !NA"<.tijhEhX!{(e* 6 +xA:NP "跢 HQoan'%ol}F,:a1auV#d鶪B(*Jشo%Ԏ?ETDlenQ:a.&1# ^tD9GJ iGDy$u->۴DQNY" GC!⧸] ӊZGBA";#DD. hc[m!#:kHJ#  ɗ`D##$+J *mMiULвnF$*lE=H HZ#A;mذh$DuiHP I q# "Yn!䂤4GDtZ#twȏ $]ADtmDJ㎋H@譱MDDRH)%GNA A]hȫiLI'iPN"9:GE:PRdD4L"GdrLrcsR3*L't">GqHI UH 9 $°!hBCh;xtؤN"#4yI ^+ DG@!#YChGDs!HqCh ‚(pEĺEXN +d"2XI莈IHE8VЈtS~0A$|q DF B! +@tNFiu`@v;/ +BP /A +H$-$EC!H- ђt7X_B-J$tذ DXkGV"7qUІ۸oV- S0>vJKl"<(Jaivt WCm":PmIV 75iS]w Б+eR^uOjulM&dڨIpتxa]>IC 0Ec&.a=:"4 #ӳmTB*BE jؙ":z>#}R#E2H0#@t9PgAH-$j 1 BjXP9RHރnP;6@XmBHHD~*d -4ۉ@&zL7v~M6c`ʒHW. Zo#U$u &ӭ"?@+H6Q[-Ն}-I_bOma$t;(>:ֈ.MGE݄@TeBxnkIه֛`ǴntAi +aBNx";{I$r#oŴ9ЪA؊P~24xtTGAvӷ B)i}6v'":#GUxn -JuDtGAzk i idy7k^ a$t&E; Ӷa I#7m A@$G8BP 4(@t 64D_ + IH="] 6 DuC@3mGFq.BSrPa("֘J#Er PB9n&sM$DsI dB(MtnJ!zH dtP 0el]EE]I_$IH Bo">" +H $x +:P/Xbgn4NB !* N QVNU0Dh!p$FufVj".vNi"G"莈i a+n& ӽQ:}:P#FU$#s+AKKrԇE_gfi$tXG !#x" \ZI#fّHaIplM8eL)H4_I!tAD|AGPh B" &Ӷdtt]Y2Cڈ Um%zph< bIL1 N  AAC]( +vzm\FBB< Vi6fà ( vݲfa2>aEԧ Tpڇ !H{XI_۠êAnn 3ce Wn ut +#HBKDuLtjĂgnH{ 47]\D#t"&ABl?zh4Gޭ"?' *Ru4I4)wh^ւL1u] #ôja;">mSЊPQRWa k8& dRDu*rMԳ'BW#hB sa D|A9OxIV#gi4iDtG@ &J P \G[ duwP^""$v`Ci&#O; +X GEI#"%o=DPB,!pBAA + VI+MqƐ4ASAgCDp"ޚTNQ Aڸzuؓz]D @$K;AV$LWЄ%Aߤb.4TioHI=OhHugՠ#EzJA)ЗD"Ƒ|J⠘ ">GD}DvF0lB:xƃ]7DtW~ua I!r$H( I$GUa FHP80@E:X RhCh i,vHt"""&{BGF.c #:i"A  I"$DtYg/v:rb'DFHI*he`+p C:#IbG4$![MI+@#xa!&a`h$ i ]'AaR:i ]mJ 1.DRpj[\b4ç ":#8Tidq#Dt b-C`3wJ!B I":.q\r4#JٔZ:>HAR5xa:b@&n[N"""QAIwDtnTR:H_GS+az,Nۤa  9 #^paGݤI1I")7 ZD!MVH+G3 hGm~aH`ҥeH zP@XTm3d%W 5mt?VeoD6]\'T&sc<4.6Z ضa&IV@+lI؄ [L:HHaТ9Ҧ!AR A!vXE&H#T۾^wifB F,MF @k{I"<^k޶':PI#h"莐#iCduMa&@$AaiXtӱ%W !Qm$2+`#Mm$W JĨu E + *Uv& EŢ4a-jU̎ &awBAi)HBHg* a`Dj \X[B#A$HCdoiLzyG3dGDy&jOh D4DtE]A4">֐6)(# ƼQ($~Lʄ' +.M%ł.#ADDEj:#RK&z&NU"/[Ҩc@ChEGEB $vKcni +OiwM'I$pEҍ$EG붓z p؋Ovv% #fVL*I +G"Ha9;P0ECvE*IPD|KA+m7b4GDvIP $mRo(m:v=EU">GBAAꞪV M\H">y*&nmDdim-͙r)Ilr:N j$GR=B$tGDs9ziT 5TŤN( @Hi"SdtmGz}C=(GB ]$vv"U$M~t؂(u5MPM&#YA :Ix2l3mM?0YhZIv˭Ttݲ?TA4&!բ E %7E檚{V@CgBM#P  ZANi ͢9 @#nW]2zEݶyHuaȢAMoih">mh">6/zku$Es#l==Φ @#3NumT@D~*b\ L*"NP3 o}X0ǧMLt\>F1i!}|X҉L!T| R. WMAL*-dBDhDFKᷦMj#D0b'7nKݠfAT !HZr:P zjNyME:H F! CMlDt,",SMA+K 06BL i"`&WՔf)A&6m+)T-% K]$  0 b:DtFaId.æ۠7}U]t(=*#'08&i8a0–qp%V$+9kA$W:`IH[VV $ +! (|ZFBD`ͳ-T ,6RlKZTӑy b i`AG'i]*̋zA$4݃>!@&$sJ VoB HCA4&Mh&h0$ i DD$G';RMzL= ďܴ +":P)h.fvĂq#I ) HA)02<]WgސDiA:A ͢ "(ʢ.m%I!qEAGA%EA$Ga+ jP! u  E(rhծn7Hi#:R:S#Ź m$HNqA4-##E$&Qڹg#AAbGB!^#th%0HZLi6:bd)3JitâSIQ׈6 +@ݑD 6M̹$Pb\!' &Q4 4,%h":A#P껃h'ABaM.B>j~I%|,6tHe}^؍'#M)4";#kR$4d@mGk+*Y𜅷l$YT"pρS*Bm0GPgER!q#[dGV0AAt'qBm1m"ꐇPFt"*GA#A&(sr M&6 nWbv8D}%4~"1R:V6PЋuAҪA!azm؉pMݥmVa70O@莅H4GM ۹:xI @b#>A5 Н}](WDH!tvGVXjӐ#i(֯uڠo#m#Vھwۻr:H7@4xami0cl#M"`ӥ֛I}4XE:t2EHE|)ж@l;¶ B- ##H @\EQ]ꭌ:mL7Gchm( EBd##L8A$p4 ]Dt#y(m#|(bٖ H# A 'I#(;ݢm #?IeVD8vA + B yN܏i:vQ]": H%d/A H!&A +)$ҫA쎄9q $"8ZEA "kM5Рtz["4"$xe # $5N/M@GahmC Æm )ݫ(L=1'_PE0AҠD%H1AE#JКg`h$vؑҨt&ԉA A tqC MM(MJ T]#CaBqmt&?) I:H.$à"$xI H $iA!A2Ɩ Uq*!#HYQHFÑJaA""$y莾a|7A$" HZ AjЈ$WՔ9[H5莋A[Z@ 6 P$:B ) I$y:.1#tBEm8TL/uI"<"_#4@1+oMb1hIi6 Ф $ 6tB hJuTMhXBsA$#U (mhRqӵ DtWLC*q.șbB)(":C}AN.K于QC]@T8PILQC0GTQvPDMRMFGIGDr ,i&QH0*:M"::"PiG@ +GHB-3>}xMi8e 7:= Ir>G:<#`DCa(Y)feH7 +008-- A!#΄R. SHCg`aED|#Z {G61dt]my$@CtN""4a씔:#!]#DEHSq `b_Dv]|#V0j)ԖZR##( $G 1 wx`$vz@@COVulaЎaGACQtujIPڌ#"iA1m :#bI$:N# 28Pa_AV'#-9(r +}E~U8;6ZUmv#,Մ+r[,het BqBN*-Gh2;XA"Y]Y A$ņ };I+ TLUOn0AA AJ6f8 I A TAEl7T4EqL2+@4"G2MvE*v @DvADSA@A&8AIGJ,iCT to9# 莝"=M"8tGPi;GtLvA&>d +I VPpPP+ $XvTEPm\l36&m4"$A tT% ma#((7IA:hDDI ^uHnJIE '" :Be h3)PˤjRPM$V 3$nDt#7IhhVAA+#:H ά4DD#}ޙ~ +&E;fFS@PR/ SjbIJY۠X":#%!Dt7-ûmfұt$ հqPؗAq ZU~44!'hza:AIChQ&ijH@a&H+@B4GMI֚OnmJVVJEDv_/G!t젨:IhANA">,&UI íl-*GSިgJ $AI!i$'Tja;h wpلʖfnVݻA5{JA]QgZNTA^@*u4v>n@J +TM0L PN fp!D#: GL ZDp v 2E +!Em+9CIHh,m ,6bVj†IHC#!(ɷMrA: !]+Q8>"]8A ٌYfom+b""(6 4KaۺE1 qs6"Gdz'b@A ;T"5JńRVA$.@$A=QHG_w +ݱiR $I&7NeHUXt")-a_mbu%]S#w#aԍ-ՠ"#$)4 Jq#*I˦"7L2G SGIǨܳH L$:#"e}QtG҈DPI6 $;T *V#hG p]-xH Dy +VA b(6MDx$+VA!r #. o!((0zN1#,IP@6NIT NCeZ#5d9tAar#Ȏ* HVN쁢: jA!#tG&ĿgbI9tH̱A{M I$$~A D$} F$i2t*H$ 8F%DA8EhVI9콅š$ "?PP_qaRX(reJHE&-m!-%%0)+YC9XM_a8!1#V $0*^b٩+f::}bGA$!M#pIz%,pA9Cu iAlAںlC@2K9W"$VQ#1TDvaSm+s DD$aAb$m&DtvN)! ֡ u0ۡg2*d[i%Bv-D`H#5:HONm!lHjl$,+gٜa^D:# ;HH%ҪN^4;F" &Nʵn .:āi ‹I&[eGfց:/V j۠!.t"2:#EQ* $8g(MV$ JeTdnSr!HE C[Јl A R<=*UbݝJT82=`-r#|H][aRA2:## Zm1es6!94CKB,vVP%D{t2hI+Abx(}a(&C":# $VhFMH6iVa670}Ј#xI(pRƆ7IA +B-|#V΄RJLvDveBٵNY5\nl DujPťmJ҇:VW(u 0;5F qJl!.E]5EiAahDd#*X I$+yIIݥ"/"# 67m@l ʂ uy6TREh">ޑ̭R +I04Z@#G\b $G}EP2cޗ Sl Z4(vAXA1.$0uZ.UaG@C#I-NI (;ul3*@f(J$GNHZI](|' nP" 6ct(,H!#cgb3tNmSpqPH$G`MhU!vI' H ($.t  +o#0a:aXC-m+b,=jH:HGTKK:ԫmӖSD%фo<C CA>g# gDGA!Q ME:N!#Ny  +؍$bGT7W,4 :@.GE֔HnkP+tC˥E[-TI";H4!ahA6BDq@G* +}8`I:m#earߚHDA!.[ ":e +*| &A$&! C!RIUA0CMBfJL2Jmk +ÂR}xh$S;#tyeD] MfFv$\ˢ;1㸋tbDPX`# *) [T 9 0 ʀ#m#A"e[vx I$_# ȺHB"8,*+bE(r8" Zq+m(raƶJVHT I"< j'HDq!I8D}\]m*wnJi4M E u m'*IFDфGEA$G:.r::*7)d gi8 $(JLD;M(B#0hm0 B!!!$MW K9DiA2:OA5DDD$۴,+H4B!#Zj#MGa9 /'Vz#"j6Rd V֖mY" jY"Xm."WU F0ED}[L +a¬& WAH'AGM:cĝJFmh$⚆)7ihETEFE>h4G2&u0#>*VB-[c-$tIȫ@/*.ꈮTG6m 6FRL $]MфGE^J̄ 5b&jᴑSBG[YI]FJ#! "? $$2֓ Du`DC:!lM:BGQob@kv# b#A$ߤ, JB]@EqtTX>~(a꺆iHӻt#:VVVOe-HDjނ WwRM.ІZEpt݄"Ri6@l%zЇHH t,$ϱki[IkP>KNBt,0Azn[EhցR 8mh&ʺ$ tm":IV":{n նv!(7a* +/6R]VnT6S$0t}": 47kJ&+H0i];a<(LA:W#%I-P`菗@',ŬVU} ʶA2 u^bGI& O\L*eC HБNtg[@ $}82 @R.ĺ#":DLDkT.ӆQ= !FƂI">]ob!l" +Ja"!$*Ȧjբ3 +t"4" >GKݶ1U3GkNtH B)v qJPCӥiw'Һxe a֮mMŤ[nBGF M^ @Ywv&=7h C:"j :.HDX0H$dtC0M9^#s*lBK?ջMcGB "aFeYN*GuZ~h*&G2;.RePIʂZx$ FE:EYVDDA e +黦8A.H#PŔ8!HDDZ#s1T +h4)4G4VAa +:#E 'BhA‹b"y$]菑:6@Dt"1 +DXH$#hGCb" $#>GEuEZ]!a$s#Fj [j[ &菂Dr#h'T2]7B"""Dv!.#$'M$ FDs#](`i&DD#GDtGeGFwf",EɛB ʲ^+#l#DBa"DBGKI0kT H$0(QNh"a +A@#:#t(#D( @b=/bGA"" AH#v"91"OCb @V"<"!! A=05Td Ո"""enLDGBGD~4B ^Lm}Ј`[ZeGt B#{ڭ2:ŵ@GYVL$AtmVeկڤB]'ZUKkRՋ ZVMe6&z(^!0۶a5Z醒 .w[M[ih6ZzL">T wVإWz Rӳ4*AQZX$AAndG9%橇m{nʖB"j#ta+"莋#g:hoKH!t]fEC ADtEЋ][i7u0*":#@CI֐4GA AERwn*}3!i Ͳh2u["> :@!I/H4B"v#e6߾ІI6F%oI7ꄿAZME&VivVӦޭMҭӱoJmaaH;j_{oPUm":]I'#ڻA=]+ b޷ MeQk2H}%nذҭӪmQHHjGV!]XaGdiofUYYi0!g*.l H$Kf Gq@mMrA#zahL>]C8*KtE}h:DyAB#m]ł7Ds tCi8E>CIR#k? :.@Ci"쎅~A6^Է#8tGF5HD3BnEHXL7H2a<7IPwbʨmhn쭕b'XkDtMDuI"l6GOw`A c|1:Td6"mZvi@I @$_#t]]ekNT# #A-En = +J% H KI$^M0NiD A@nI8a 3A5L?n>*A%NZm.]&ֽ.菑:na |¤,6U & ":j H T$]lCij' A"*"InEA=JE0 "klI)1qHA +T m EGV&0#M$ &" @$$W`Y:)I&ܐ^:xKl5, 5;IoWp1 !hR圞 iO| +)-:TچDG!a۴:&ҳ %Ӯ PDuMݩHdtGM.g VV@D,(m%$ I HRA atm_x:2YeRLA"ϵDGB"($քC+aAp +G5HDOiI4%ucq ؈r:jݔ"I*ёyG)g(si5lCBzt0}M7O(0MEITItZL aHP'۾:I Ziϱ":e +]6L*H7aG#H"4St;-X֟m$tڑРF7v)_TGZ駶v ꡵Һ%8HEI6UHHPnn-̒vT1B0m#2OS/F2G\[Ui[aڊCi (-ؤ]$֐UM&S۪pAې6yRI/Vivn7h#Exj uMC n +@!mj鵧ZtC2߆vIE:}֊.Kwۧq-dm\j,+P 7HݶVPEs̸\;ZiCQ!tGEh8F]qtM ӰA~+4A$qEH# I tݠii+i6GDtI}R $W"0H7Mm^Dh莂 $gntHH {-"6$Bc[L:FIIaYݨDM[m%IEѴ]菄":S-[*A);mM\D$A"GF"166Sn,⪘ A龕i9.L!:#;A +vAA4phB;ziSi*wiGHDDR Xb:DtA JgomN,㨄&d"i1.sn⑒uKT5A[]ot؅Q \LBB'vC 4C\ "[cWaM:V!l3WA&":iD @ m *wgфIi. i&a|*J,$%fYު vS*ȶT[M& ۆc6 ؊BT@RJ'1en":EzM}Y[%/- +Yt ՙ\f! 4Dta +GB u+2bt+24X VP!PTf9&2٢$h1 0r`[2";IE8A"%hHr]\L4 M$"H6"Co#:#l  a I@GGA"")z}+"(,娎EA(rGNX@:>4ّLH$: 9gA06N#4 +-pA(u-oI 2A(B*/jiX2:<%!:ALLIڠ`"SODuC ZiIQeHb#t :} ;Ut4C) jIꓷGVmaBHCPE:.aA曫RXm$Dx!&] aDt_n`NGEN*J AXTڑV); o $xåVi;Yg(vaMU)-Dt_Hk{) FH䒍/$GAySH[~TUbIXgf:a&DwʣA7eOLȔr$VEn ,!#w{B Gr_tGd|CH+|%U#:nQN|;&U"oG":M6Ոy#GB3O +d[ f$DZ eI $P"9 I 0HUde8v()$(Sa2氐 B)$GE%V|TCD|a!vA# i4 J R1H4A2:#>GDqHADu҃B#kA bInh ]&J $Dt#in#SW0""7fJ(9CEq";aE5Gd8Xv'@A6Wh| +U#:Mh@D(莕#P'HB%d40ރ-t-4 +pi˪MDD0) ΘaaK$ ml"2)T҈#P :NȳlH0 jyga@И@ @.J0*@hzյA$""":ED|MN +B$tёnniSWBH$ n Ǹ0JhD*#`۴-A:LEH02AE- YXhێr1$dt'v!nH$1VD& 6$ތ?H ZD}0vFc0y_LCfK:K I(ΜHF8L#F0A6NI$Ɲ` +i R:gG)ʰaR#&`!1JDVt):ҋH$t"B2[EVC l iEWJ4gեB=iԒə:*H$g\A@y0Dy/#da˰E((YJ";#(PB9E0 itG׊bʆ#A% F35Dt ӈ A"$#Bdz:#AHH>_T#!ʌB"/B$t%(A uDl g$IA4AQ8@qdE" LʗψTD*d}; l0HU,b.I%dA6Գ AE3  +duWL12I$fFDG#,W 8N)I> l&b)$;rADtGdv,4%H 6YA2tXUIlKvނAR#"!mA dmL.M$GLV8J*ij,0E2"0CFF%:*Z&~YEb?mhM25Dt3 bA-9H1Q<hVx"?P +`@H$aZE('I:P4gt@N-$~!LHAs@AٙNQVLcaZ 4(  + A">E>)1H2VL+>9DE6Tm̖  wGGI+bRb!#tGAzB-%p쎈\x!8r-H%&}!`PH ͢8$%>$a0 H$+H@%FI[{ $Ej !{ !Xs8B" 0$Bq| #A + hDDRN$3 +mC+"* L%(u}!VV} b,!q6 %OĎ"::CMM" dt_a(r ":MnޚY_T"8A0DtL)[}mJ $²:Z4BA {YA$" I /"<)8GNNv +@$+HN$Y7(- ?7 0@0I "<+$?$tB194WAj AIغ:8F4SlCvtW!KpD Am bg_K#4+bNt-VqtI#4A$p8Ma +xA$ )$@( LA4h#KՊDLM:ڡII#"*#m M4 Uu`uS]ݙS7" +POZA7RA .DtXKLR `Eҍ-xuCDtd4H'*$:72$VN`""E&AXDtqGEtPIʠDtz fDBG#@) LIvJ$GI]Ѹ$+GY".IIHB12TR>w}( Dv&oRQA`DDA8"<Ղ +YաC<$MF4B 2CtAL!MTˌ0ȮF̕/ Aj6XT"/HR',!>"GA cB $GY$`TݵAa˂Lv##.6dWYtOA"<"E ]$G6zu *ake:"9|(q@Et:M0 WbGA 8A#PV`8*f:ILBDvGB4G[uJ#moov"qˣh!d8+:6K D|P+m"JPGu^"ڤ7tA(*++(A +UFJH$ۆjD%H"tG@$7vNKgVF U#H*Dx5Vj҂#VqɎSWElV&ӌ XCM-oT[XH$GA*J/.t-bSie75vxI."7¶r@@ٯ":+BK۶u=M!H@tLi=;{ Vmմ;MڿAV-VOwnݻ#NںDu֛"<'Yc4_Ih6j6iDt8o}"?S &PZAjxi[IdY" 7:`# r!6=Y#( =6êniӤA$ib=pt ""фG|}uKzB"GA2A4wH$k:Dt A%1@CBDSz 6AM1@-i6@;ƛnT# +)PئRct"b tvv -eqxB-t.[q.ơ@Rn^k6JDjwi /rʖq)a_=KH.'SF݄tA4>4Ӷ"DqDv!GbݫN610Dt<NFYDqv 0{aBHDwMkU"oINΉi";j4$"çL6&Gwe:uh/h6(zLjOVdDs/ INzp\sHB]Hꋤ PB:#]m7V4F+ m ӖpTSjT5m5;lY@OVrl;0 wAmTdNIMhoEW2XV 7"Ɲv+u 3 :.(gvl&PM|I +fAxP h#A%nIDІI t"GB8.a2(p0v"9QT&"Ьf݄@I$ EU$|I#r # % $ڶtDt4L1vH $8FHGPD¨ .AX"IP@BB"ҏ,!Le#h:#:u: B"%?ܳ1e,´Ҵ.i$;B!Yz(rtBGYAmD!#mV-TDB>~! !#hD"1Q DupnaS/[l+dpQEӵPA , Age7vMiH6**!$xHHA3Zm2M(A+mWγoM'xm*U +ƐK8*m2Mi FuM20m^8#vZU,HD 뺺c6 )74k:Aź%uU lFղyQ #ES/'FZoKH$Aښ{HX#q B[({jd%ӝ"tG鉦 uдvHD#xd&=i3=KuG Aljb,"?#HXF;%Yp0kjЈ0."#̅Pl{W#ڊd$D/SuC^D҄m&ķZ׼7_A$+j5D~ #tWMC]tաa hxiig[M tMRau(~%&H]sa$a9͒:$tÈL$!/[A>'mWa7暖p65ߺWbou24I7{֐E=[k[{dY I-EAuI`BCcM=4)n#"l}ҰLv(uq:iZh}RIЈf m]\*"^՜DutGDtBMkA֠"8FA=MS(r(sB=666BGE7&N NAj֟e=8Dw1!r-*"<'a EBin uMvI&҄ 4,qto>Dx7P$GNA$ uΑ'x#AaL7ګEr 6n۠A0 +El$GAJ @HA [aB" ;[DtӤi_+:zm?=]ES o] +m5I"GPMPm'K?{* i6<-8@K/lmDmD_^-սUMԇa8I]$hm#4v6n=Xk":#*6,/dD}"屰È`6؆#J*Kn6! vL7BBHS\EmCEk8 EZLӫzaWhEZ +!  :o"@$tGDknE3k .k@Nm00G@@#%Y +^BH"=(0JEA cA";(sNUj"xUI H H">J +S +vh B I$!:{$}ZGH!{(şz1:!A"Z#PHKTq|#<#CAf2:mGCKEgA#w@@s1@ !WhD!Hk>}Ҿ嶦%A`%D1V!1 莄 F#HDBH. q_Өҩm4$ul vGF E J $AgمwA(p"=uKKUgؕֆ%~ۑh%V!+qIc +endstream +endobj +1 0 obj +<< +/Producer (MFPImgLib V3.5) +/CreationDate (D:20130709142703+01'00') +/Creator (TOSHIBA e-STUDIO520) +>> +endobj +2 0 obj +<< +/Type /Catalog +/Pages 3 0 R +>> +endobj +3 0 obj +<< +/Type /Pages +/Kids [ 4 0 R ] +/Count 1 +>> +endobj +xref +0 8 +0000000000 65535 f +0000043625 00000 n +0000043744 00000 n +0000043793 00000 n +0000000009 00000 n +0000000160 00000 n +0000000249 00000 n +0000000279 00000 n +trailer +<< +/Size 8 +/Info 1 0 R +/Root 2 0 R +>> +startxref +43852 +%%EOF diff --git a/plot.py b/plot.py index 611583c..9843bc1 100644 --- a/plot.py +++ b/plot.py @@ -1,32 +1,10 @@ -from mpl_toolkits.mplot3d import Axes3D -import matplotlib.pyplot as plt import numpy as np +import matplotlib.pyplot as plt +from math import e -fig = plt.figure() -#ax = Axes3D(fig) - -#X = np.arange(-20, 20, 0.5) -#xlen = len(X) -#Y = np.arange(-20, 20, 0.5) -#ylen = len(Y) -#X, Y = np.meshgrid(X, Y) - -#fig = plt.figure() -#for i in [-0.3]: -# j = i*i -# Z = 2*X*Y*i*(4-j) + (X*X+Y*Y)*j*(6-2*j) -# surf = ax.plot_surface(X, Y, Z, rstride=1, cstride=1, -# linewidth=0, antialiased=True) - -#ax = fig.add_subplot(1,1,1) -#x = np.arange(-1,5,0.1) -#y = (((4*x -24)*x +36)*x-16)*x -#z = 0*x -#ax.plot(x,y,x,z,antialiased=True) - -ax = fig.add_subplot(1,1,1) -x = np.arange(0,1,0.01) -y = np.sqrt((x-1)*(x+2)/((x+1)*(x-2))) -ax.plot(x,y) - +t = np.arange(0.001, 1, 0.001) +u = np.sqrt((4*e**2 + 4*e +1)*t**2+ (24*e**2-4*e+4)*t+ 36*e**2-24*e+4)/(2*(e-1)*t)-(3*e-1)/((e-1)*t) +print u[0] +print t[0] +plt.plot(t,u) plt.show() -- cgit v1.2.3-70-g09d2 From 50900bfc44961b87379cd2d3464b677d9f5be1ac Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sat, 21 Sep 2013 18:16:12 -0400 Subject: Converting to LATIN format --- .gitignore | 3 + abbrvnat.bst | 1436 +++++++++++++++++++++++++++++++++++++++++++++++++ abstract.txt | 28 + abstract_latin.tex | 27 + approximation.tex | 11 +- definitions.tex | 21 +- intro.tex | 2 +- llncs.cls | 1207 +++++++++++++++++++++++++++++++++++++++++ main.tex | 8 +- paper.tex | 29 +- problem.tex | 9 +- related.tex | 2 +- splncs.bst | 1098 ++++++++++++++++++++++++++++++++++++++ splncsnat.bst | 1508 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 14 files changed, 5353 insertions(+), 36 deletions(-) create mode 100644 abbrvnat.bst create mode 100644 abstract.txt create mode 100644 abstract_latin.tex create mode 100644 llncs.cls create mode 100644 splncs.bst create mode 100644 splncsnat.bst diff --git a/.gitignore b/.gitignore index 73b4789..b6f82fe 100644 --- a/.gitignore +++ b/.gitignore @@ -5,4 +5,7 @@ *.blg *.out *.brf +*.gz +*.fls +*.fdb_latexmk /*.pdf diff --git a/abbrvnat.bst b/abbrvnat.bst new file mode 100644 index 0000000..6109cb7 --- /dev/null +++ b/abbrvnat.bst @@ -0,0 +1,1436 @@ +%% File: `abbrvnat.bst' +%% A modification of `abbrv.bst' for use with natbib package +%% +%% Copyright 1993-2007 Patrick W Daly +%% Max-Planck-Institut f\"ur Sonnensystemforschung +%% Max-Planck-Str. 2 +%% D-37191 Katlenburg-Lindau +%% Germany +%% E-mail: daly@mps.mpg.de +%% +%% This program can be redistributed and/or modified under the terms +%% of the LaTeX Project Public License Distributed from CTAN +%% archives in directory macros/latex/base/lppl.txt; either +%% version 1 of the License, or any later version. +%% + % Version and source file information: + % \ProvidesFile{natbst.mbs}[2007/11/26 1.93 (PWD)] + % + % BibTeX `plainnat' family + % version 0.99b for BibTeX versions 0.99a or later, + % for LaTeX versions 2.09 and 2e. + % + % For use with the `natbib.sty' package; emulates the corresponding + % member of the `plain' family, but with author-year citations. + % + % With version 6.0 of `natbib.sty', it may also be used for numerical + % citations, while retaining the commands \citeauthor, \citefullauthor, + % and \citeyear to print the corresponding information. + % + % For version 7.0 of `natbib.sty', the KEY field replaces missing + % authors/editors, and the date is left blank in \bibitem. + % + % Includes field EID for the sequence/citation number of electronic journals + % which is used instead of page numbers. + % + % Includes fields ISBN and ISSN. + % + % Includes field URL for Internet addresses. + % + % Includes field DOI for Digital Object Idenfifiers. + % + % Works best with the url.sty package of Donald Arseneau. + % + % Works with identical authors and year are further sorted by + % citation key, to preserve any natural sequence. + % +ENTRY + { address + author + booktitle + chapter + doi + eid + edition + editor + howpublished + institution + isbn + issn + journal + key + month + note + number + organization + pages + publisher + school + series + title + type + url + volume + year + } + {} + { label extra.label sort.label short.list } + +INTEGERS { output.state before.all mid.sentence after.sentence after.block } + +FUNCTION {init.state.consts} +{ #0 'before.all := + #1 'mid.sentence := + #2 'after.sentence := + #3 'after.block := +} + +STRINGS { s t } + +FUNCTION {output.nonnull} +{ 's := + output.state mid.sentence = + { ", " * write$ } + { output.state after.block = + { add.period$ write$ + newline$ + "\newblock " write$ + } + { output.state before.all = + 'write$ + { add.period$ " " * write$ } + if$ + } + if$ + mid.sentence 'output.state := + } + if$ + s +} + +FUNCTION {output} +{ duplicate$ empty$ + 'pop$ + 'output.nonnull + if$ +} + +FUNCTION {output.check} +{ 't := + duplicate$ empty$ + { pop$ "empty " t * " in " * cite$ * warning$ } + 'output.nonnull + if$ +} + +FUNCTION {fin.entry} +{ add.period$ + write$ + newline$ +} + +FUNCTION {new.block} +{ output.state before.all = + 'skip$ + { after.block 'output.state := } + if$ +} + +FUNCTION {new.sentence} +{ output.state after.block = + 'skip$ + { output.state before.all = + 'skip$ + { after.sentence 'output.state := } + if$ + } + if$ +} + +FUNCTION {not} +{ { #0 } + { #1 } + if$ +} + +FUNCTION {and} +{ 'skip$ + { pop$ #0 } + if$ +} + +FUNCTION {or} +{ { pop$ #1 } + 'skip$ + if$ +} + +FUNCTION {new.block.checka} +{ empty$ + 'skip$ + 'new.block + if$ +} + +FUNCTION {new.block.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.block + if$ +} + +FUNCTION {new.sentence.checka} +{ empty$ + 'skip$ + 'new.sentence + if$ +} + +FUNCTION {new.sentence.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.sentence + if$ +} + +FUNCTION {field.or.null} +{ duplicate$ empty$ + { pop$ "" } + 'skip$ + if$ +} + +FUNCTION {emphasize} +{ duplicate$ empty$ + { pop$ "" } + { "\emph{" swap$ * "}" * } + if$ +} + +INTEGERS { nameptr namesleft numnames } + +FUNCTION {format.names} +{ 's := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr "{f.~}{vv~}{ll}{, jj}" format.name$ 't := + nameptr #1 > + { namesleft #1 > + { ", " * t * } + { numnames #2 > + { "," * } + 'skip$ + if$ + t "others" = + { " et~al." * } + { " and " * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {format.key} +{ empty$ + { key field.or.null } + { "" } + if$ +} + +FUNCTION {format.authors} +{ author empty$ + { "" } + { author format.names } + if$ +} + +FUNCTION {format.editors} +{ editor empty$ + { "" } + { editor format.names + editor num.names$ #1 > + { ", editors" * } + { ", editor" * } + if$ + } + if$ +} + +FUNCTION {format.isbn} +{ isbn empty$ + { "" } + { new.block "ISBN " isbn * } + if$ +} + +FUNCTION {format.issn} +{ issn empty$ + { "" } + { new.block "ISSN " issn * } + if$ +} + +FUNCTION {format.url} +{ url empty$ + { "" } + { new.block "URL \url{" url * "}" * } + if$ +} + +FUNCTION {format.doi} +{ doi empty$ + { "" } + { new.block "\doi{" doi * "}" * } + if$ +} + +FUNCTION {format.title} +{ title empty$ + { "" } + { title "t" change.case$ } + if$ +} + +FUNCTION {format.full.names} +{'s := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr + "{vv~}{ll}" format.name$ 't := + nameptr #1 > + { + namesleft #1 > + { ", " * t * } + { + numnames #2 > + { "," * } + 'skip$ + if$ + t "others" = + { " et~al." * } + { " and " * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {author.editor.full} +{ author empty$ + { editor empty$ + { "" } + { editor format.full.names } + if$ + } + { author format.full.names } + if$ +} + +FUNCTION {author.full} +{ author empty$ + { "" } + { author format.full.names } + if$ +} + +FUNCTION {editor.full} +{ editor empty$ + { "" } + { editor format.full.names } + if$ +} + +FUNCTION {make.full.names} +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.full + { type$ "proceedings" = + 'editor.full + 'author.full + if$ + } + if$ +} + +FUNCTION {output.bibitem} +{ newline$ + "\bibitem[" write$ + label write$ + ")" make.full.names duplicate$ short.list = + { pop$ } + { * } + if$ + "]{" * write$ + cite$ write$ + "}" write$ + newline$ + "" + before.all 'output.state := +} + +FUNCTION {n.dashify} +{ 't := + "" + { t empty$ not } + { t #1 #1 substring$ "-" = + { t #1 #2 substring$ "--" = not + { "--" * + t #2 global.max$ substring$ 't := + } + { { t #1 #1 substring$ "-" = } + { "-" * + t #2 global.max$ substring$ 't := + } + while$ + } + if$ + } + { t #1 #1 substring$ * + t #2 global.max$ substring$ 't := + } + if$ + } + while$ +} + +FUNCTION {format.date} +{ year duplicate$ empty$ + { "empty year in " cite$ * warning$ + pop$ "" } + 'skip$ + if$ + month empty$ + 'skip$ + { month + " " * swap$ * + } + if$ + extra.label * +} + +FUNCTION {format.btitle} +{ title emphasize +} + +FUNCTION {tie.or.space.connect} +{ duplicate$ text.length$ #3 < + { "~" } + { " " } + if$ + swap$ * * +} + +FUNCTION {either.or.check} +{ empty$ + 'pop$ + { "can't use both " swap$ * " fields in " * cite$ * warning$ } + if$ +} + +FUNCTION {format.bvolume} +{ volume empty$ + { "" } + { "volume" volume tie.or.space.connect + series empty$ + 'skip$ + { " of " * series emphasize * } + if$ + "volume and number" number either.or.check + } + if$ +} + +FUNCTION {format.number.series} +{ volume empty$ + { number empty$ + { series field.or.null } + { output.state mid.sentence = + { "number" } + { "Number" } + if$ + number tie.or.space.connect + series empty$ + { "there's a number but no series in " cite$ * warning$ } + { " in " * series * } + if$ + } + if$ + } + { "" } + if$ +} + +FUNCTION {format.edition} +{ edition empty$ + { "" } + { output.state mid.sentence = + { edition "l" change.case$ " edition" * } + { edition "t" change.case$ " edition" * } + if$ + } + if$ +} + +INTEGERS { multiresult } + +FUNCTION {multi.page.check} +{ 't := + #0 'multiresult := + { multiresult not + t empty$ not + and + } + { t #1 #1 substring$ + duplicate$ "-" = + swap$ duplicate$ "," = + swap$ "+" = + or or + { #1 'multiresult := } + { t #2 global.max$ substring$ 't := } + if$ + } + while$ + multiresult +} + +FUNCTION {format.pages} +{ pages empty$ + { "" } + { pages multi.page.check + { "pages" pages n.dashify tie.or.space.connect } + { "page" pages tie.or.space.connect } + if$ + } + if$ +} + +FUNCTION {format.eid} +{ eid empty$ + { "" } + { "art." eid tie.or.space.connect } + if$ +} + +FUNCTION {format.vol.num.pages} +{ volume field.or.null + number empty$ + 'skip$ + { "\penalty0 (" number * ")" * * + volume empty$ + { "there's a number but no volume in " cite$ * warning$ } + 'skip$ + if$ + } + if$ + pages empty$ + 'skip$ + { duplicate$ empty$ + { pop$ format.pages } + { ":\penalty0 " * pages n.dashify * } + if$ + } + if$ +} + +FUNCTION {format.vol.num.eid} +{ volume field.or.null + number empty$ + 'skip$ + { "\penalty0 (" number * ")" * * + volume empty$ + { "there's a number but no volume in " cite$ * warning$ } + 'skip$ + if$ + } + if$ + eid empty$ + 'skip$ + { duplicate$ empty$ + { pop$ format.eid } + { ":\penalty0 " * eid * } + if$ + } + if$ +} + +FUNCTION {format.chapter.pages} +{ chapter empty$ + 'format.pages + { type empty$ + { "chapter" } + { type "l" change.case$ } + if$ + chapter tie.or.space.connect + pages empty$ + 'skip$ + { ", " * format.pages * } + if$ + } + if$ +} + +FUNCTION {format.in.ed.booktitle} +{ booktitle empty$ + { "" } + { editor empty$ + { "In " booktitle emphasize * } + { "In " format.editors * ", " * booktitle emphasize * } + if$ + } + if$ +} + +FUNCTION {empty.misc.check} +{ author empty$ title empty$ howpublished empty$ + month empty$ year empty$ note empty$ + and and and and and + key empty$ not and + { "all relevant fields are empty in " cite$ * warning$ } + 'skip$ + if$ +} + +FUNCTION {format.thesis.type} +{ type empty$ + 'skip$ + { pop$ + type "t" change.case$ + } + if$ +} + +FUNCTION {format.tr.number} +{ type empty$ + { "Technical Report" } + 'type + if$ + number empty$ + { "t" change.case$ } + { number tie.or.space.connect } + if$ +} + +FUNCTION {format.article.crossref} +{ key empty$ + { journal empty$ + { "need key or journal for " cite$ * " to crossref " * crossref * + warning$ + "" + } + { "In \emph{" journal * "}" * } + if$ + } + { "In " } + if$ + " \citet{" * crossref * "}" * +} + +FUNCTION {format.book.crossref} +{ volume empty$ + { "empty volume in " cite$ * "'s crossref of " * crossref * warning$ + "In " + } + { "Volume" volume tie.or.space.connect + " of " * + } + if$ + editor empty$ + editor field.or.null author field.or.null = + or + { key empty$ + { series empty$ + { "need editor, key, or series for " cite$ * " to crossref " * + crossref * warning$ + "" * + } + { "\emph{" * series * "}" * } + if$ + } + 'skip$ + if$ + } + 'skip$ + if$ + " \citet{" * crossref * "}" * +} + +FUNCTION {format.incoll.inproc.crossref} +{ editor empty$ + editor field.or.null author field.or.null = + or + { key empty$ + { booktitle empty$ + { "need editor, key, or booktitle for " cite$ * " to crossref " * + crossref * warning$ + "" + } + { "In \emph{" booktitle * "}" * } + if$ + } + { "In " } + if$ + } + { "In " } + if$ + " \citet{" * crossref * "}" * +} + +FUNCTION {article} +{ output.bibitem + format.authors "author" output.check + author format.key output + new.block + format.title "title" output.check + new.block + crossref missing$ + { journal emphasize "journal" output.check + eid empty$ + { format.vol.num.pages output } + { format.vol.num.eid output } + if$ + format.date "year" output.check + } + { format.article.crossref output.nonnull + eid empty$ + { format.pages output } + { format.eid output } + if$ + } + if$ + format.issn output + format.doi output + format.url output + new.block + note output + fin.entry +} + +FUNCTION {book} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check + editor format.key output + } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + new.block + format.btitle "title" output.check + crossref missing$ + { format.bvolume output + new.block + format.number.series output + new.sentence + publisher "publisher" output.check + address output + } + { new.block + format.book.crossref output.nonnull + } + if$ + format.edition output + format.date "year" output.check + format.isbn output + format.doi output + format.url output + new.block + note output + fin.entry +} + +FUNCTION {booklet} +{ output.bibitem + format.authors output + author format.key output + new.block + format.title "title" output.check + howpublished address new.block.checkb + howpublished output + address output + format.date output + format.isbn output + format.doi output + format.url output + new.block + note output + fin.entry +} + +FUNCTION {inbook} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check + editor format.key output + } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + new.block + format.btitle "title" output.check + crossref missing$ + { format.bvolume output + format.chapter.pages "chapter and pages" output.check + new.block + format.number.series output + new.sentence + publisher "publisher" output.check + address output + } + { format.chapter.pages "chapter and pages" output.check + new.block + format.book.crossref output.nonnull + } + if$ + format.edition output + format.date "year" output.check + format.isbn output + format.doi output + format.url output + new.block + note output + fin.entry +} + +FUNCTION {incollection} +{ output.bibitem + format.authors "author" output.check + author format.key output + new.block + format.title "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.bvolume output + format.number.series output + format.chapter.pages output + new.sentence + publisher "publisher" output.check + address output + format.edition output + format.date "year" output.check + } + { format.incoll.inproc.crossref output.nonnull + format.chapter.pages output + } + if$ + format.isbn output + format.doi output + format.url output + new.block + note output + fin.entry +} + +FUNCTION {inproceedings} +{ output.bibitem + format.authors "author" output.check + author format.key output + new.block + format.title "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.bvolume output + format.number.series output + format.pages output + address empty$ + { organization publisher new.sentence.checkb + organization output + publisher output + format.date "year" output.check + } + { address output.nonnull + format.date "year" output.check + new.sentence + organization output + publisher output + } + if$ + } + { format.incoll.inproc.crossref output.nonnull + format.pages output + } + if$ + format.isbn output + format.doi output + format.url output + new.block + note output + fin.entry +} + +FUNCTION {conference} { inproceedings } + +FUNCTION {manual} +{ output.bibitem + format.authors output + author format.key output + new.block + format.btitle "title" output.check + organization address new.block.checkb + organization output + address output + format.edition output + format.date output + format.url output + new.block + note output + fin.entry +} + +FUNCTION {mastersthesis} +{ output.bibitem + format.authors "author" output.check + author format.key output + new.block + format.title "title" output.check + new.block + "Master's thesis" format.thesis.type output.nonnull + school "school" output.check + address output + format.date "year" output.check + format.url output + new.block + note output + fin.entry +} + +FUNCTION {misc} +{ output.bibitem + format.authors output + author format.key output + title howpublished new.block.checkb + format.title output + howpublished new.block.checka + howpublished output + format.date output + format.issn output + format.url output + new.block + note output + fin.entry + empty.misc.check +} + +FUNCTION {phdthesis} +{ output.bibitem + format.authors "author" output.check + author format.key output + new.block + format.btitle "title" output.check + new.block + "PhD thesis" format.thesis.type output.nonnull + school "school" output.check + address output + format.date "year" output.check + format.url output + new.block + note output + fin.entry +} + +FUNCTION {proceedings} +{ output.bibitem + format.editors output + editor format.key output + new.block + format.btitle "title" output.check + format.bvolume output + format.number.series output + address output + format.date "year" output.check + new.sentence + organization output + publisher output + format.isbn output + format.doi output + format.url output + new.block + note output + fin.entry +} + +FUNCTION {techreport} +{ output.bibitem + format.authors "author" output.check + author format.key output + new.block + format.title "title" output.check + new.block + format.tr.number output.nonnull + institution "institution" output.check + address output + format.date "year" output.check + format.url output + new.block + note output + fin.entry +} + +FUNCTION {unpublished} +{ output.bibitem + format.authors "author" output.check + author format.key output + new.block + format.title "title" output.check + new.block + note "note" output.check + format.date output + format.url output + fin.entry +} + +FUNCTION {default.type} { misc } + + +MACRO {jan} {"Jan."} + +MACRO {feb} {"Feb."} + +MACRO {mar} {"Mar."} + +MACRO {apr} {"Apr."} + +MACRO {may} {"May"} + +MACRO {jun} {"June"} + +MACRO {jul} {"July"} + +MACRO {aug} {"Aug."} + +MACRO {sep} {"Sept."} + +MACRO {oct} {"Oct."} + +MACRO {nov} {"Nov."} + +MACRO {dec} {"Dec."} + + + +MACRO {acmcs} {"ACM Comput. Surv."} + +MACRO {acta} {"Acta Inf."} + +MACRO {cacm} {"Commun. ACM"} + +MACRO {ibmjrd} {"IBM J. Res. Dev."} + +MACRO {ibmsj} {"IBM Syst.~J."} + +MACRO {ieeese} {"IEEE Trans. Softw. Eng."} + +MACRO {ieeetc} {"IEEE Trans. Comput."} + +MACRO {ieeetcad} + {"IEEE Trans. Comput.-Aided Design Integrated Circuits"} + +MACRO {ipl} {"Inf. Process. Lett."} + +MACRO {jacm} {"J.~ACM"} + +MACRO {jcss} {"J.~Comput. Syst. Sci."} + +MACRO {scp} {"Sci. Comput. Programming"} + +MACRO {sicomp} {"SIAM J. Comput."} + +MACRO {tocs} {"ACM Trans. Comput. Syst."} + +MACRO {tods} {"ACM Trans. Database Syst."} + +MACRO {tog} {"ACM Trans. Gr."} + +MACRO {toms} {"ACM Trans. Math. Softw."} + +MACRO {toois} {"ACM Trans. Office Inf. Syst."} + +MACRO {toplas} {"ACM Trans. Prog. Lang. Syst."} + +MACRO {tcs} {"Theoretical Comput. Sci."} + + +READ + +FUNCTION {sortify} +{ purify$ + "l" change.case$ +} + +INTEGERS { len } + +FUNCTION {chop.word} +{ 's := + 'len := + s #1 len substring$ = + { s len #1 + global.max$ substring$ } + 's + if$ +} + +FUNCTION {format.lab.names} +{ 's := + s #1 "{vv~}{ll}" format.name$ + s num.names$ duplicate$ + #2 > + { pop$ " et~al." * } + { #2 < + 'skip$ + { s #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" = + { " et~al." * } + { " and " * s #2 "{vv~}{ll}" format.name$ * } + if$ + } + if$ + } + if$ +} + +FUNCTION {author.key.label} +{ author empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {author.editor.key.label} +{ author empty$ + { editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.lab.names } + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {author.key.organization.label} +{ author empty$ + { key empty$ + { organization empty$ + { cite$ #1 #3 substring$ } + { "The " #4 organization chop.word #3 text.prefix$ } + if$ + } + 'key + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {editor.key.organization.label} +{ editor empty$ + { key empty$ + { organization empty$ + { cite$ #1 #3 substring$ } + { "The " #4 organization chop.word #3 text.prefix$ } + if$ + } + 'key + if$ + } + { editor format.lab.names } + if$ +} + +FUNCTION {calc.short.authors} +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.key.label + { type$ "proceedings" = + 'editor.key.organization.label + { type$ "manual" = + 'author.key.organization.label + 'author.key.label + if$ + } + if$ + } + if$ + 'short.list := +} + +FUNCTION {calc.label} +{ calc.short.authors + short.list + "(" + * + year duplicate$ empty$ + short.list key field.or.null = or + { pop$ "" } + 'skip$ + if$ + * + 'label := +} + +FUNCTION {sort.format.names} +{ 's := + #1 'nameptr := + "" + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { + s nameptr "{vv{ } }{ll{ }}{ f{ }}{ jj{ }}" format.name$ 't := + nameptr #1 > + { + " " * + namesleft #1 = t "others" = and + { "zzzzz" * } + { numnames #2 > nameptr #2 = and + { "zz" * year field.or.null * " " * } + 'skip$ + if$ + t sortify * + } + if$ + } + { t sortify * } + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {sort.format.title} +{ 't := + "A " #2 + "An " #3 + "The " #4 t chop.word + chop.word + chop.word + sortify + #1 global.max$ substring$ +} + +FUNCTION {author.sort} +{ author empty$ + { key empty$ + { "to sort, need author or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {author.editor.sort} +{ author empty$ + { editor empty$ + { key empty$ + { "to sort, need author, editor, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { editor sort.format.names } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {author.organization.sort} +{ author empty$ + { organization empty$ + { key empty$ + { "to sort, need author, organization, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { "The " #4 organization chop.word sortify } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {editor.organization.sort} +{ editor empty$ + { organization empty$ + { key empty$ + { "to sort, need editor, organization, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { "The " #4 organization chop.word sortify } + if$ + } + { editor sort.format.names } + if$ +} + + +FUNCTION {presort} +{ calc.label + label sortify + " " + * + type$ "book" = + type$ "inbook" = + or + 'author.editor.sort + { type$ "proceedings" = + 'editor.organization.sort + { type$ "manual" = + 'author.organization.sort + 'author.sort + if$ + } + if$ + } + if$ + " " + * + year field.or.null sortify + * + " " + * + cite$ + * + #1 entry.max$ substring$ + 'sort.label := + sort.label * + #1 entry.max$ substring$ + 'sort.key$ := +} + +ITERATE {presort} + +SORT + +STRINGS { longest.label last.label next.extra } + +INTEGERS { longest.label.width last.extra.num number.label } + +FUNCTION {initialize.longest.label} +{ "" 'longest.label := + #0 int.to.chr$ 'last.label := + "" 'next.extra := + #0 'longest.label.width := + #0 'last.extra.num := + #0 'number.label := +} + +FUNCTION {forward.pass} +{ last.label label = + { last.extra.num #1 + 'last.extra.num := + last.extra.num int.to.chr$ 'extra.label := + } + { "a" chr.to.int$ 'last.extra.num := + "" 'extra.label := + label 'last.label := + } + if$ + number.label #1 + 'number.label := +} + +FUNCTION {reverse.pass} +{ next.extra "b" = + { "a" 'extra.label := } + 'skip$ + if$ + extra.label 'next.extra := + extra.label + duplicate$ empty$ + 'skip$ + { "{\natexlab{" swap$ * "}}" * } + if$ + 'extra.label := + label extra.label * 'label := +} + +EXECUTE {initialize.longest.label} + +ITERATE {forward.pass} + +REVERSE {reverse.pass} + +FUNCTION {bib.sort.order} +{ sort.label 'sort.key$ := +} + +ITERATE {bib.sort.order} + +SORT + +FUNCTION {begin.bib} +{ preamble$ empty$ + 'skip$ + { preamble$ write$ newline$ } + if$ + "\begin{thebibliography}{" number.label int.to.str$ * "}" * + write$ newline$ + "\providecommand{\natexlab}[1]{#1}" + write$ newline$ + "\providecommand{\url}[1]{\texttt{#1}}" + write$ newline$ + "\expandafter\ifx\csname urlstyle\endcsname\relax" + write$ newline$ + " \providecommand{\doi}[1]{doi: #1}\else" + write$ newline$ + " \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi" + write$ newline$ +} + +EXECUTE {begin.bib} + +EXECUTE {init.state.consts} + +ITERATE {call.type$} + +FUNCTION {end.bib} +{ newline$ + "\end{thebibliography}" write$ newline$ +} + +EXECUTE {end.bib} diff --git a/abstract.txt b/abstract.txt new file mode 100644 index 0000000..9078926 --- /dev/null +++ b/abstract.txt @@ -0,0 +1,28 @@ +In the classical experimental design setting, an experimenter E has access to +a population of n potential experiment subjects each associated +with a vector of features x_i. Conducting an experiment with subject i +reveals an unknown value y_i E. E typically assumes some hypothetical +relationship between x_i and y_i, e.g., y_i = β*x_i, and estimates β from +experiments, e.g., through linear regression. As a proxy for various practical +constraints, E may select only a subset of subjects on which to conduct the +experiment. + +We initiate the study of budgeted mechanisms for experimental design. In +this setting, E has a budget B. Each subject i declares an associated cost +c_i to be part of the experiment, and must be paid at least her cost. In +particular, the Experimental Design Problem (EDP) is to find a set S of subjects +for the experiment that maximizes V(S) = log det(I_d + \sum_{i\in S} x_i x_i^T ) +under the constraint \sum_{i\in S} c_i ≤ B; our objective function corresponds to the information +gain in parameter β that is learned through linear regression methods, and +is related to the so-called D-optimality criterion. Further, the subjects are +strategic and may lie about their costs. Thus, we need to design a mechanism +for EDP with suitable properties. + +We present a deterministic, polynomial time, budget feasible mechanism +scheme, that is approximately truthful and yields a constant (= 12.98) factor +approximation to EDP. By applying previous work on budget feasible mechanisms +with a submodular objective, one could only have derived either an +exponential time deterministic mechanism or a randomized polynomial time +mechanism. We also establish that no truthful, budget-feasible mechanism is +possible within a factor 2 approximation, and show how to generalize our approach +to a wide class of learning problems, beyond linear regression. diff --git a/abstract_latin.tex b/abstract_latin.tex new file mode 100644 index 0000000..04ec9fe --- /dev/null +++ b/abstract_latin.tex @@ -0,0 +1,27 @@ +\documentclass{llncs} +\usepackage[numbers]{natbib} +\usepackage[utf8]{inputenc} +\usepackage{amsmath,amsfonts} +\usepackage{algorithm, algpseudocode} +\usepackage{bbm,color,verbatim} +\input{definitions} +\usepackage[pagebackref=true,breaklinks=true,colorlinks=true]{hyperref} +\title{Budget Feasible Mechanisms\\ for Experimental Design} +\author{ + Thibaut Horel\inst{1} + \and + Stratis Ioannidis\inst{2} + \and + S. Muthukrishnan\inst{3} +} +\institute{Harvard University, \email{thibaut.horel@normalesup.org} + \and + Technicolor, \email{stratis.ioannidis@technicolor.com} + \and + Rutgers University, \email{muthu@cs.rutgers.edu} +} +\begin{document} +\maketitle +\vspace{2em} +\input{abstract} +\end{document} diff --git a/approximation.tex b/approximation.tex index 4978279..3e3f482 100644 --- a/approximation.tex +++ b/approximation.tex @@ -47,7 +47,7 @@ expectation of $V$ under the distribution $P_\mathcal{N}^\lambda$: F(\lambda) \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big] % = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) -= \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right],\qquad \lambda\in[0,1]^n. += \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right],\quad \lambda\in[0,1]^n. \end{equation} Function $F$ is an extension of $V$ to the domain $[0,1]^n$, as it equals $V$ on integer inputs: $F(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. %\citeN{pipage} have shown how to use this extension to obtain approximation guarantees for an interesting class of optimization problems through the \emph{pipage rounding} framework, which has been successfully applied in \citeN{chen, singer-influence}. @@ -55,9 +55,12 @@ Contrary to problems such as \textsc{Knapsack}, the multi-linear extension \eqref{eq:multi-linear} cannot be optimized in polynomial time for the value function $V$ we study here, given by \eqref{modified}. Hence, we introduce an extension $L:[0,1]^n\to\reals$ s.t.~ \begin{equation}\label{eq:our-relaxation} -\quad L(\lambda) \defeq -\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right)= -\log\det\left(\mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right), \qquad \lambda\in[0,1]^n. + \begin{split} + L(\lambda) &\defeq +\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right)\\ +&= \log\det\left(\mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right), +\quad \lambda\in[0,1]^n. +\end{split} \end{equation} Note that $L$ also extends $V$, and follows naturally from the multi-linear extension by swapping the expectation and $\log \det$ in \eqref{eq:multi-linear}. Crucially, it is \emph{strictly concave} on $[0,1]^n$, a fact that we exploit in the next section to maximize $L$ subject to the budget constraint in polynomial time. diff --git a/definitions.tex b/definitions.tex index 7d30dcd..236c368 100644 --- a/definitions.tex +++ b/definitions.tex @@ -1,14 +1,14 @@ \newcommand{\mutual}{\ensuremath{{I}}} \newcommand{\entropy}{\ensuremath{{H}}} -\newtheorem{lemma}{Lemma} -\newtheorem{proposition}{Proposition} -\newtheorem{fact}{Fact} -\newtheorem{example}{Example} -\newtheorem{prop}{Proposition} -\newtheorem{theorem}{Theorem} -\newtheorem{corollary}{Corollary} -\theoremstyle{definition} -\newtheorem{definition}{Definition} +%\newtheorem{lemma}{Lemma} +%\newtheorem{proposition}{Proposition} +%\newtheorem{fact}{Fact} +%\newtheorem{example}{Example} +%\newtheorem{prop}{Proposition} +%\newtheorem{theorem}{Theorem} +%\newtheorem{corollary}{Corollary} +%\theoremstyle{definition} +%\newtheorem{definition}{Definition} \newcommand{\citeN}{\citet} %\newcommand*{\defeq}{\stackrel{\text{def}}{=}} \newcommand*{\defeq}{\equiv} @@ -36,7 +36,8 @@ \newcommand{\junk}[1]{} \newcommand{\edp}{{\tt EDP}} \newcommand{\dom}{\mathcal{D}} -\newcommand{\note}[1]{\textcolor{red}{#1}} +\newcommand{\qedhere}{\qed} +%\newcommand{\note}[1]{\textcolor{red}{#1}} \algrenewcommand\algorithmicrequire{\textbf{Input:}} \algrenewcommand\algorithmicensure{\textbf{Output:}} diff --git a/intro.tex b/intro.tex index 1d07f48..2519ac4 100644 --- a/intro.tex +++ b/intro.tex @@ -42,7 +42,7 @@ We present a polynomial time mechanism scheme for \SEDP{} that is approximately In contrast to this, we show that no truthful, budget-feasible mechanisms are possible for \SEDP{} within a factor 2 approximation. \smallskip -We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results on budget feasible mechanism design under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time, or a non-deterministic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded). +We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results on budget feasible mechanism design under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time, or a non-determi\-nis\-tic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded). \end{itemize} diff --git a/llncs.cls b/llncs.cls new file mode 100644 index 0000000..1d49f3d --- /dev/null +++ b/llncs.cls @@ -0,0 +1,1207 @@ +% LLNCS DOCUMENT CLASS -- version 2.17 (12-Jul-2010) +% Springer Verlag LaTeX2e support for Lecture Notes in Computer Science +% +%% +%% \CharacterTable +%% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z +%% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z +%% Digits \0\1\2\3\4\5\6\7\8\9 +%% Exclamation \! Double quote \" Hash (number) \# +%% Dollar \$ Percent \% Ampersand \& +%% Acute accent \' Left paren \( Right paren \) +%% Asterisk \* Plus \+ Comma \, +%% Minus \- Point \. Solidus \/ +%% Colon \: Semicolon \; Less than \< +%% Equals \= Greater than \> Question mark \? +%% Commercial at \@ Left bracket \[ Backslash \\ +%% Right bracket \] Circumflex \^ Underscore \_ +%% Grave accent \` Left brace \{ Vertical bar \| +%% Right brace \} Tilde \~} +%% +\NeedsTeXFormat{LaTeX2e}[1995/12/01] +\ProvidesClass{llncs}[2010/07/12 v2.17 +^^J LaTeX document class for Lecture Notes in Computer Science] +% Options +\let\if@envcntreset\iffalse +\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue} +\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y} +\DeclareOption{oribibl}{\let\oribibl=Y} +\let\if@custvec\iftrue +\DeclareOption{orivec}{\let\if@custvec\iffalse} +\let\if@envcntsame\iffalse +\DeclareOption{envcountsame}{\let\if@envcntsame\iftrue} +\let\if@envcntsect\iffalse +\DeclareOption{envcountsect}{\let\if@envcntsect\iftrue} +\let\if@runhead\iffalse +\DeclareOption{runningheads}{\let\if@runhead\iftrue} + +\let\if@openright\iftrue +\let\if@openbib\iffalse +\DeclareOption{openbib}{\let\if@openbib\iftrue} + +% languages +\let\switcht@@therlang\relax +\def\ds@deutsch{\def\switcht@@therlang{\switcht@deutsch}} +\def\ds@francais{\def\switcht@@therlang{\switcht@francais}} + +\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}} + +\ProcessOptions + +\LoadClass[twoside]{article} +\RequirePackage{multicol} % needed for the list of participants, index +\RequirePackage{aliascnt} + +\setlength{\textwidth}{12.2cm} +\setlength{\textheight}{19.3cm} +\renewcommand\@pnumwidth{2em} +\renewcommand\@tocrmarg{3.5em} +% +\def\@dottedtocline#1#2#3#4#5{% + \ifnum #1>\c@tocdepth \else + \vskip \z@ \@plus.2\p@ + {\leftskip #2\relax \rightskip \@tocrmarg \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \parindent #2\relax\@afterindenttrue + \interlinepenalty\@M + \leavevmode + \@tempdima #3\relax + \advance\leftskip \@tempdima \null\nobreak\hskip -\leftskip + {#4}\nobreak + \leaders\hbox{$\m@th + \mkern \@dotsep mu\hbox{.}\mkern \@dotsep + mu$}\hfill + \nobreak + \hb@xt@\@pnumwidth{\hfil\normalfont \normalcolor #5}% + \par}% + \fi} +% +\def\switcht@albion{% +\def\abstractname{Abstract.} +\def\ackname{Acknowledgement.} +\def\andname{and} +\def\lastandname{\unskip, and} +\def\appendixname{Appendix} +\def\chaptername{Chapter} +\def\claimname{Claim} +\def\conjecturename{Conjecture} +\def\contentsname{Table of Contents} +\def\corollaryname{Corollary} +\def\definitionname{Definition} +\def\examplename{Example} +\def\exercisename{Exercise} +\def\figurename{Fig.} +\def\keywordname{{\bf Keywords:}} +\def\indexname{Index} +\def\lemmaname{Lemma} +\def\contriblistname{List of Contributors} +\def\listfigurename{List of Figures} +\def\listtablename{List of Tables} +\def\mailname{{\it Correspondence to\/}:} +\def\noteaddname{Note added in proof} +\def\notename{Note} +\def\partname{Part} +\def\problemname{Problem} +\def\proofname{Proof} +\def\propertyname{Property} +\def\propositionname{Proposition} +\def\questionname{Question} +\def\remarkname{Remark} +\def\seename{see} +\def\solutionname{Solution} +\def\subclassname{{\it Subject Classifications\/}:} +\def\tablename{Table} +\def\theoremname{Theorem}} +\switcht@albion +% Names of theorem like environments are already defined +% but must be translated if another language is chosen +% +% French section +\def\switcht@francais{%\typeout{On parle francais.}% + \def\abstractname{R\'esum\'e.}% + \def\ackname{Remerciements.}% + \def\andname{et}% + \def\lastandname{ et}% + \def\appendixname{Appendice} + \def\chaptername{Chapitre}% + \def\claimname{Pr\'etention}% + \def\conjecturename{Hypoth\`ese}% + \def\contentsname{Table des mati\`eres}% + \def\corollaryname{Corollaire}% + \def\definitionname{D\'efinition}% + \def\examplename{Exemple}% + \def\exercisename{Exercice}% + \def\figurename{Fig.}% + \def\keywordname{{\bf Mots-cl\'e:}} + \def\indexname{Index} + \def\lemmaname{Lemme}% + \def\contriblistname{Liste des contributeurs} + \def\listfigurename{Liste des figures}% + \def\listtablename{Liste des tables}% + \def\mailname{{\it Correspondence to\/}:} + \def\noteaddname{Note ajout\'ee \`a l'\'epreuve}% + \def\notename{Remarque}% + \def\partname{Partie}% + \def\problemname{Probl\`eme}% + \def\proofname{Preuve}% + \def\propertyname{Caract\'eristique}% +%\def\propositionname{Proposition}% + \def\questionname{Question}% + \def\remarkname{Remarque}% + \def\seename{voir} + \def\solutionname{Solution}% + \def\subclassname{{\it Subject Classifications\/}:} + \def\tablename{Tableau}% + \def\theoremname{Th\'eor\`eme}% +} +% +% German section +\def\switcht@deutsch{%\typeout{Man spricht deutsch.}% + \def\abstractname{Zusammenfassung.}% + \def\ackname{Danksagung.}% + \def\andname{und}% + \def\lastandname{ und}% + \def\appendixname{Anhang}% + \def\chaptername{Kapitel}% + \def\claimname{Behauptung}% + \def\conjecturename{Hypothese}% + \def\contentsname{Inhaltsverzeichnis}% + \def\corollaryname{Korollar}% +%\def\definitionname{Definition}% + \def\examplename{Beispiel}% + \def\exercisename{\"Ubung}% + \def\figurename{Abb.}% + \def\keywordname{{\bf Schl\"usselw\"orter:}} + \def\indexname{Index} +%\def\lemmaname{Lemma}% + \def\contriblistname{Mitarbeiter} + \def\listfigurename{Abbildungsverzeichnis}% + \def\listtablename{Tabellenverzeichnis}% + \def\mailname{{\it Correspondence to\/}:} + \def\noteaddname{Nachtrag}% + \def\notename{Anmerkung}% + \def\partname{Teil}% +%\def\problemname{Problem}% + \def\proofname{Beweis}% + \def\propertyname{Eigenschaft}% +%\def\propositionname{Proposition}% + \def\questionname{Frage}% + \def\remarkname{Anmerkung}% + \def\seename{siehe} + \def\solutionname{L\"osung}% + \def\subclassname{{\it Subject Classifications\/}:} + \def\tablename{Tabelle}% +%\def\theoremname{Theorem}% +} + +% Ragged bottom for the actual page +\def\thisbottomragged{\def\@textbottom{\vskip\z@ plus.0001fil +\global\let\@textbottom\relax}} + +\renewcommand\small{% + \@setfontsize\small\@ixpt{11}% + \abovedisplayskip 8.5\p@ \@plus3\p@ \@minus4\p@ + \abovedisplayshortskip \z@ \@plus2\p@ + \belowdisplayshortskip 4\p@ \@plus2\p@ \@minus2\p@ + \def\@listi{\leftmargin\leftmargini + \parsep 0\p@ \@plus1\p@ \@minus\p@ + \topsep 8\p@ \@plus2\p@ \@minus4\p@ + \itemsep0\p@}% + \belowdisplayskip \abovedisplayskip +} + +\frenchspacing +\widowpenalty=10000 +\clubpenalty=10000 + +\setlength\oddsidemargin {63\p@} +\setlength\evensidemargin {63\p@} +\setlength\marginparwidth {90\p@} + +\setlength\headsep {16\p@} + +\setlength\footnotesep{7.7\p@} +\setlength\textfloatsep{8mm\@plus 2\p@ \@minus 4\p@} +\setlength\intextsep {8mm\@plus 2\p@ \@minus 2\p@} + +\setcounter{secnumdepth}{2} + +\newcounter {chapter} +\renewcommand\thechapter {\@arabic\c@chapter} + +\newif\if@mainmatter \@mainmattertrue +\newcommand\frontmatter{\cleardoublepage + \@mainmatterfalse\pagenumbering{Roman}} +\newcommand\mainmatter{\cleardoublepage + \@mainmattertrue\pagenumbering{arabic}} +\newcommand\backmatter{\if@openright\cleardoublepage\else\clearpage\fi + \@mainmatterfalse} + +\renewcommand\part{\cleardoublepage + \thispagestyle{empty}% + \if@twocolumn + \onecolumn + \@tempswatrue + \else + \@tempswafalse + \fi + \null\vfil + \secdef\@part\@spart} + +\def\@part[#1]#2{% + \ifnum \c@secnumdepth >-2\relax + \refstepcounter{part}% + \addcontentsline{toc}{part}{\thepart\hspace{1em}#1}% + \else + \addcontentsline{toc}{part}{#1}% + \fi + \markboth{}{}% + {\centering + \interlinepenalty \@M + \normalfont + \ifnum \c@secnumdepth >-2\relax + \huge\bfseries \partname~\thepart + \par + \vskip 20\p@ + \fi + \Huge \bfseries #2\par}% + \@endpart} +\def\@spart#1{% + {\centering + \interlinepenalty \@M + \normalfont + \Huge \bfseries #1\par}% + \@endpart} +\def\@endpart{\vfil\newpage + \if@twoside + \null + \thispagestyle{empty}% + \newpage + \fi + \if@tempswa + \twocolumn + \fi} + +\newcommand\chapter{\clearpage + \thispagestyle{empty}% + \global\@topnum\z@ + \@afterindentfalse + \secdef\@chapter\@schapter} +\def\@chapter[#1]#2{\ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \refstepcounter{chapter}% + \typeout{\@chapapp\space\thechapter.}% + \addcontentsline{toc}{chapter}% + {\protect\numberline{\thechapter}#1}% + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \chaptermark{#1}% + \addtocontents{lof}{\protect\addvspace{10\p@}}% + \addtocontents{lot}{\protect\addvspace{10\p@}}% + \if@twocolumn + \@topnewpage[\@makechapterhead{#2}]% + \else + \@makechapterhead{#2}% + \@afterheading + \fi} +\def\@makechapterhead#1{% +% \vspace*{50\p@}% + {\centering + \ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \large\bfseries \@chapapp{} \thechapter + \par\nobreak + \vskip 20\p@ + \fi + \fi + \interlinepenalty\@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} +\def\@schapter#1{\if@twocolumn + \@topnewpage[\@makeschapterhead{#1}]% + \else + \@makeschapterhead{#1}% + \@afterheading + \fi} +\def\@makeschapterhead#1{% +% \vspace*{50\p@}% + {\centering + \normalfont + \interlinepenalty\@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} + +\renewcommand\section{\@startsection{section}{1}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {12\p@ \@plus 4\p@ \@minus 4\p@}% + {\normalfont\large\bfseries\boldmath + \rightskip=\z@ \@plus 8em\pretolerance=10000 }} +\renewcommand\subsection{\@startsection{subsection}{2}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {8\p@ \@plus 4\p@ \@minus 4\p@}% + {\normalfont\normalsize\bfseries\boldmath + \rightskip=\z@ \@plus 8em\pretolerance=10000 }} +\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {-0.5em \@plus -0.22em \@minus -0.1em}% + {\normalfont\normalsize\bfseries\boldmath}} +\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}% + {-12\p@ \@plus -4\p@ \@minus -4\p@}% + {-0.5em \@plus -0.22em \@minus -0.1em}% + {\normalfont\normalsize\itshape}} +\renewcommand\subparagraph[1]{\typeout{LLNCS warning: You should not use + \string\subparagraph\space with this class}\vskip0.5cm +You should not use \verb|\subparagraph| with this class.\vskip0.5cm} + +\DeclareMathSymbol{\Gamma}{\mathalpha}{letters}{"00} +\DeclareMathSymbol{\Delta}{\mathalpha}{letters}{"01} +\DeclareMathSymbol{\Theta}{\mathalpha}{letters}{"02} +\DeclareMathSymbol{\Lambda}{\mathalpha}{letters}{"03} +\DeclareMathSymbol{\Xi}{\mathalpha}{letters}{"04} +\DeclareMathSymbol{\Pi}{\mathalpha}{letters}{"05} +\DeclareMathSymbol{\Sigma}{\mathalpha}{letters}{"06} +\DeclareMathSymbol{\Upsilon}{\mathalpha}{letters}{"07} +\DeclareMathSymbol{\Phi}{\mathalpha}{letters}{"08} +\DeclareMathSymbol{\Psi}{\mathalpha}{letters}{"09} +\DeclareMathSymbol{\Omega}{\mathalpha}{letters}{"0A} + +\let\footnotesize\small + +\if@custvec +\def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle#1$}} +{\mbox{\boldmath$\textstyle#1$}} +{\mbox{\boldmath$\scriptstyle#1$}} +{\mbox{\boldmath$\scriptscriptstyle#1$}}} +\fi + +\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}} +\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil +\penalty50\hskip1em\null\nobreak\hfil\squareforqed +\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi} + +\def\getsto{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr\gets\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +\gets\cr\to\cr}}}}} +\def\lid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr<\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr<\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr<\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +<\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\gid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr>\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr>\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\grole{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr +>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.8pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.3pt}<\cr}}}}} +\def\bbbr{{\rm I\!R}} %reelle Zahlen +\def\bbbm{{\rm I\!M}} +\def\bbbn{{\rm I\!N}} %natuerliche Zahlen +\def\bbbf{{\rm I\!F}} +\def\bbbh{{\rm I\!H}} +\def\bbbk{{\rm I\!K}} +\def\bbbp{{\rm I\!P}} +\def\bbbone{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} +{\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}} +\def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}} +\def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbs{{\mathchoice +{\setbox0=\hbox{$\displaystyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}} +\def\bbbz{{\mathchoice {\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\scriptstyle Z\kern-0.3em Z$}} +{\hbox{$\mathsf\scriptscriptstyle Z\kern-0.2em Z$}}}} + +\let\ts\, + +\setlength\leftmargini {17\p@} +\setlength\leftmargin {\leftmargini} +\setlength\leftmarginii {\leftmargini} +\setlength\leftmarginiii {\leftmargini} +\setlength\leftmarginiv {\leftmargini} +\setlength \labelsep {.5em} +\setlength \labelwidth{\leftmargini} +\addtolength\labelwidth{-\labelsep} + +\def\@listI{\leftmargin\leftmargini + \parsep 0\p@ \@plus1\p@ \@minus\p@ + \topsep 8\p@ \@plus2\p@ \@minus4\p@ + \itemsep0\p@} +\let\@listi\@listI +\@listi +\def\@listii {\leftmargin\leftmarginii + \labelwidth\leftmarginii + \advance\labelwidth-\labelsep + \topsep 0\p@ \@plus2\p@ \@minus\p@} +\def\@listiii{\leftmargin\leftmarginiii + \labelwidth\leftmarginiii + \advance\labelwidth-\labelsep + \topsep 0\p@ \@plus\p@\@minus\p@ + \parsep \z@ + \partopsep \p@ \@plus\z@ \@minus\p@} + +\renewcommand\labelitemi{\normalfont\bfseries --} +\renewcommand\labelitemii{$\m@th\bullet$} + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\def\tableofcontents{\chapter*{\contentsname\@mkboth{{\contentsname}}% + {{\contentsname}}} + \def\authcount##1{\setcounter{auco}{##1}\setcounter{@auth}{1}} + \def\lastand{\ifnum\value{auco}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{auco}% + \lastand + \else + \unskip, + \fi}% + \@starttoc{toc}\if@restonecol\twocolumn\fi} + +\def\l@part#1#2{\addpenalty{\@secpenalty}% + \addvspace{2em plus\p@}% % space above part line + \begingroup + \parindent \z@ + \rightskip \z@ plus 5em + \hrule\vskip5pt + \large % same size as for a contribution heading + \bfseries\boldmath % set line in boldface + \leavevmode % TeX command to enter horizontal mode. + #1\par + \vskip5pt + \hrule + \vskip1pt + \nobreak % Never break after part entry + \endgroup} + +\def\@dotsep{2} + +\let\phantomsection=\relax + +\def\hyperhrefextend{\ifx\hyper@anchor\@undefined\else +{}\fi} + +\def\addnumcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{\protect\numberline + {\thechapter}#3}{\thepage}\hyperhrefextend}}% +\def\addcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{\thepage}\hyperhrefextend}}% +\def\addcontentsmarkwop#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{0}\hyperhrefextend}}% + +\def\@adcmk[#1]{\ifcase #1 \or +\def\@gtempa{\addnumcontentsmark}% + \or \def\@gtempa{\addcontentsmark}% + \or \def\@gtempa{\addcontentsmarkwop}% + \fi\@gtempa{toc}{chapter}% +} +\def\addtocmark{% +\phantomsection +\@ifnextchar[{\@adcmk}{\@adcmk[3]}% +} + +\def\l@chapter#1#2{\addpenalty{-\@highpenalty} + \vskip 1.0em plus 1pt \@tempdima 1.5em \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip + {\large\bfseries\boldmath#1}\ifx0#2\hfil\null + \else + \nobreak + \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern + \@dotsep mu$}\hfill + \nobreak\hbox to\@pnumwidth{\hss #2}% + \fi\par + \penalty\@highpenalty \endgroup} + +\def\l@title#1#2{\addpenalty{-\@highpenalty} + \addvspace{8pt plus 1pt} + \@tempdima \z@ + \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip + #1\nobreak + \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern + \@dotsep mu$}\hfill + \nobreak\hbox to\@pnumwidth{\hss #2}\par + \penalty\@highpenalty \endgroup} + +\def\l@author#1#2{\addpenalty{\@highpenalty} + \@tempdima=15\p@ %\z@ + \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima %\hskip -\leftskip + \textit{#1}\par + \penalty\@highpenalty \endgroup} + +\setcounter{tocdepth}{0} +\newdimen\tocchpnum +\newdimen\tocsecnum +\newdimen\tocsectotal +\newdimen\tocsubsecnum +\newdimen\tocsubsectotal +\newdimen\tocsubsubsecnum +\newdimen\tocsubsubsectotal +\newdimen\tocparanum +\newdimen\tocparatotal +\newdimen\tocsubparanum +\tocchpnum=\z@ % no chapter numbers +\tocsecnum=15\p@ % section 88. plus 2.222pt +\tocsubsecnum=23\p@ % subsection 88.8 plus 2.222pt +\tocsubsubsecnum=27\p@ % subsubsection 88.8.8 plus 1.444pt +\tocparanum=35\p@ % paragraph 88.8.8.8 plus 1.666pt +\tocsubparanum=43\p@ % subparagraph 88.8.8.8.8 plus 1.888pt +\def\calctocindent{% +\tocsectotal=\tocchpnum +\advance\tocsectotal by\tocsecnum +\tocsubsectotal=\tocsectotal +\advance\tocsubsectotal by\tocsubsecnum +\tocsubsubsectotal=\tocsubsectotal +\advance\tocsubsubsectotal by\tocsubsubsecnum +\tocparatotal=\tocsubsubsectotal +\advance\tocparatotal by\tocparanum} +\calctocindent + +\def\l@section{\@dottedtocline{1}{\tocchpnum}{\tocsecnum}} +\def\l@subsection{\@dottedtocline{2}{\tocsectotal}{\tocsubsecnum}} +\def\l@subsubsection{\@dottedtocline{3}{\tocsubsectotal}{\tocsubsubsecnum}} +\def\l@paragraph{\@dottedtocline{4}{\tocsubsubsectotal}{\tocparanum}} +\def\l@subparagraph{\@dottedtocline{5}{\tocparatotal}{\tocsubparanum}} + +\def\listoffigures{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn + \fi\section*{\listfigurename\@mkboth{{\listfigurename}}{{\listfigurename}}} + \@starttoc{lof}\if@restonecol\twocolumn\fi} +\def\l@figure{\@dottedtocline{1}{0em}{1.5em}} + +\def\listoftables{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn + \fi\section*{\listtablename\@mkboth{{\listtablename}}{{\listtablename}}} + \@starttoc{lot}\if@restonecol\twocolumn\fi} +\let\l@table\l@figure + +\renewcommand\listoffigures{% + \section*{\listfigurename + \@mkboth{\listfigurename}{\listfigurename}}% + \@starttoc{lof}% + } + +\renewcommand\listoftables{% + \section*{\listtablename + \@mkboth{\listtablename}{\listtablename}}% + \@starttoc{lot}% + } + +\ifx\oribibl\undefined +\ifx\citeauthoryear\undefined +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \def\@biblabel##1{##1.} + \small + \list{\@biblabel{\@arabic\c@enumiv}}% + {\settowidth\labelwidth{\@biblabel{#1}}% + \leftmargin\labelwidth + \advance\leftmargin\labelsep + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{\@arabic\c@enumiv}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`\.=\@m} + {\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} +\def\@lbibitem[#1]#2{\item[{[#1]}\hfill]\if@filesw + {\let\protect\noexpand\immediate + \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} +\newcount\@tempcntc +\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi + \@tempcnta\z@\@tempcntb\m@ne\def\@citea{}\@cite{\@for\@citeb:=#2\do + {\@ifundefined + {b@\@citeb}{\@citeo\@tempcntb\m@ne\@citea\def\@citea{,}{\bfseries + ?}\@warning + {Citation `\@citeb' on page \thepage \space undefined}}% + {\setbox\z@\hbox{\global\@tempcntc0\csname b@\@citeb\endcsname\relax}% + \ifnum\@tempcntc=\z@ \@citeo\@tempcntb\m@ne + \@citea\def\@citea{,}\hbox{\csname b@\@citeb\endcsname}% + \else + \advance\@tempcntb\@ne + \ifnum\@tempcntb=\@tempcntc + \else\advance\@tempcntb\m@ne\@citeo + \@tempcnta\@tempcntc\@tempcntb\@tempcntc\fi\fi}}\@citeo}{#1}} +\def\@citeo{\ifnum\@tempcnta>\@tempcntb\else + \@citea\def\@citea{,\,\hskip\z@skip}% + \ifnum\@tempcnta=\@tempcntb\the\@tempcnta\else + {\advance\@tempcnta\@ne\ifnum\@tempcnta=\@tempcntb \else + \def\@citea{--}\fi + \advance\@tempcnta\m@ne\the\@tempcnta\@citea\the\@tempcntb}\fi\fi} +\else +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \small + \list{}% + {\settowidth\labelwidth{}% + \leftmargin\parindent + \itemindent=-\parindent + \labelsep=\z@ + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`\.=\@m} + {\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} + \def\@cite#1{#1}% + \def\@lbibitem[#1]#2{\item[]\if@filesw + {\def\protect##1{\string ##1\space}\immediate + \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} + \fi +\else +\@cons\@openbib@code{\noexpand\small} +\fi + +\def\idxquad{\hskip 10\p@}% space that divides entry from number + +\def\@idxitem{\par\hangindent 10\p@} + +\def\subitem{\par\setbox0=\hbox{--\enspace}% second order + \noindent\hangindent\wd0\box0}% index entry + +\def\subsubitem{\par\setbox0=\hbox{--\,--\enspace}% third + \noindent\hangindent\wd0\box0}% order index entry + +\def\indexspace{\par \vskip 10\p@ plus5\p@ minus3\p@\relax} + +\renewenvironment{theindex} + {\@mkboth{\indexname}{\indexname}% + \thispagestyle{empty}\parindent\z@ + \parskip\z@ \@plus .3\p@\relax + \let\item\par + \def\,{\relax\ifmmode\mskip\thinmuskip + \else\hskip0.2em\ignorespaces\fi}% + \normalfont\small + \begin{multicols}{2}[\@makeschapterhead{\indexname}]% + } + {\end{multicols}} + +\renewcommand\footnoterule{% + \kern-3\p@ + \hrule\@width 2truecm + \kern2.6\p@} + \newdimen\fnindent + \fnindent1em +\long\def\@makefntext#1{% + \parindent \fnindent% + \leftskip \fnindent% + \noindent + \llap{\hb@xt@1em{\hss\@makefnmark\ }}\ignorespaces#1} + +\long\def\@makecaption#1#2{% + \small + \vskip\abovecaptionskip + \sbox\@tempboxa{{\bfseries #1.} #2}% + \ifdim \wd\@tempboxa >\hsize + {\bfseries #1.} #2\par + \else + \global \@minipagefalse + \hb@xt@\hsize{\hfil\box\@tempboxa\hfil}% + \fi + \vskip\belowcaptionskip} + +\def\fps@figure{htbp} +\def\fnum@figure{\figurename\thinspace\thefigure} +\def \@floatboxreset {% + \reset@font + \small + \@setnobreak + \@setminipage +} +\def\fps@table{htbp} +\def\fnum@table{\tablename~\thetable} +\renewenvironment{table} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + \@float{table}} + {\end@float} +\renewenvironment{table*} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + \@dblfloat{table}} + {\end@dblfloat} + +\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname + ext@#1\endcsname}{#1}{\protect\numberline{\csname + the#1\endcsname}{\ignorespaces #2}}\begingroup + \@parboxrestore + \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par + \endgroup} + +% LaTeX does not provide a command to enter the authors institute +% addresses. The \institute command is defined here. + +\newcounter{@inst} +\newcounter{@auth} +\newcounter{auco} +\newdimen\instindent +\newbox\authrun +\newtoks\authorrunning +\newtoks\tocauthor +\newbox\titrun +\newtoks\titlerunning +\newtoks\toctitle + +\def\clearheadinfo{\gdef\@author{No Author Given}% + \gdef\@title{No Title Given}% + \gdef\@subtitle{}% + \gdef\@institute{No Institute Given}% + \gdef\@thanks{}% + \global\titlerunning={}\global\authorrunning={}% + \global\toctitle={}\global\tocauthor={}} + +\def\institute#1{\gdef\@institute{#1}} + +\def\institutename{\par + \begingroup + \parskip=\z@ + \parindent=\z@ + \setcounter{@inst}{1}% + \def\and{\par\stepcounter{@inst}% + \noindent$^{\the@inst}$\enspace\ignorespaces}% + \setbox0=\vbox{\def\thanks##1{}\@institute}% + \ifnum\c@@inst=1\relax + \gdef\fnnstart{0}% + \else + \xdef\fnnstart{\c@@inst}% + \setcounter{@inst}{1}% + \noindent$^{\the@inst}$\enspace + \fi + \ignorespaces + \@institute\par + \endgroup} + +\def\@fnsymbol#1{\ensuremath{\ifcase#1\or\star\or{\star\star}\or + {\star\star\star}\or \dagger\or \ddagger\or + \mathchar "278\or \mathchar "27B\or \|\or **\or \dagger\dagger + \or \ddagger\ddagger \else\@ctrerr\fi}} + +\def\inst#1{\unskip$^{#1}$} +\def\fnmsep{\unskip$^,$} +\def\email#1{{\tt#1}} +\AtBeginDocument{\@ifundefined{url}{\def\url#1{#1}}{}% +\@ifpackageloaded{babel}{% +\@ifundefined{extrasenglish}{}{\addto\extrasenglish{\switcht@albion}}% +\@ifundefined{extrasfrenchb}{}{\addto\extrasfrenchb{\switcht@francais}}% +\@ifundefined{extrasgerman}{}{\addto\extrasgerman{\switcht@deutsch}}% +}{\switcht@@therlang}% +\providecommand{\keywords}[1]{\par\addvspace\baselineskip +\noindent\keywordname\enspace\ignorespaces#1}% +} +\def\homedir{\~{ }} + +\def\subtitle#1{\gdef\@subtitle{#1}} +\clearheadinfo +% +%%% to avoid hyperref warnings +\providecommand*{\toclevel@author}{999} +%%% to make title-entry parent of section-entries +\providecommand*{\toclevel@title}{0} +% +\renewcommand\maketitle{\newpage +\phantomsection + \refstepcounter{chapter}% + \stepcounter{section}% + \setcounter{section}{0}% + \setcounter{subsection}{0}% + \setcounter{figure}{0} + \setcounter{table}{0} + \setcounter{equation}{0} + \setcounter{footnote}{0}% + \begingroup + \parindent=\z@ + \renewcommand\thefootnote{\@fnsymbol\c@footnote}% + \if@twocolumn + \ifnum \col@number=\@ne + \@maketitle + \else + \twocolumn[\@maketitle]% + \fi + \else + \newpage + \global\@topnum\z@ % Prevents figures from going at top of page. + \@maketitle + \fi + \thispagestyle{empty}\@thanks +% + \def\\{\unskip\ \ignorespaces}\def\inst##1{\unskip{}}% + \def\thanks##1{\unskip{}}\def\fnmsep{\unskip}% + \instindent=\hsize + \advance\instindent by-\headlineindent + \if!\the\toctitle!\addcontentsline{toc}{title}{\@title}\else + \addcontentsline{toc}{title}{\the\toctitle}\fi + \if@runhead + \if!\the\titlerunning!\else + \edef\@title{\the\titlerunning}% + \fi + \global\setbox\titrun=\hbox{\small\rm\unboldmath\ignorespaces\@title}% + \ifdim\wd\titrun>\instindent + \typeout{Title too long for running head. Please supply}% + \typeout{a shorter form with \string\titlerunning\space prior to + \string\maketitle}% + \global\setbox\titrun=\hbox{\small\rm + Title Suppressed Due to Excessive Length}% + \fi + \xdef\@title{\copy\titrun}% + \fi +% + \if!\the\tocauthor!\relax + {\def\and{\noexpand\protect\noexpand\and}% + \protected@xdef\toc@uthor{\@author}}% + \else + \def\\{\noexpand\protect\noexpand\newline}% + \protected@xdef\scratch{\the\tocauthor}% + \protected@xdef\toc@uthor{\scratch}% + \fi + \addtocontents{toc}{\noexpand\protect\noexpand\authcount{\the\c@auco}}% + \addcontentsline{toc}{author}{\toc@uthor}% + \if@runhead + \if!\the\authorrunning! + \value{@inst}=\value{@auth}% + \setcounter{@auth}{1}% + \else + \edef\@author{\the\authorrunning}% + \fi + \global\setbox\authrun=\hbox{\small\unboldmath\@author\unskip}% + \ifdim\wd\authrun>\instindent + \typeout{Names of authors too long for running head. Please supply}% + \typeout{a shorter form with \string\authorrunning\space prior to + \string\maketitle}% + \global\setbox\authrun=\hbox{\small\rm + Authors Suppressed Due to Excessive Length}% + \fi + \xdef\@author{\copy\authrun}% + \markboth{\@author}{\@title}% + \fi + \endgroup + \setcounter{footnote}{\fnnstart}% + \clearheadinfo} +% +\def\@maketitle{\newpage + \markboth{}{}% + \def\lastand{\ifnum\value{@inst}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{@inst}% + \lastand + \else + \unskip, + \fi}% + \begin{center}% + \let\newline\\ + {\Large \bfseries\boldmath + \pretolerance=10000 + \@title \par}\vskip .8cm +\if!\@subtitle!\else {\large \bfseries\boldmath + \vskip -.65cm + \pretolerance=10000 + \@subtitle \par}\vskip .8cm\fi + \setbox0=\vbox{\setcounter{@auth}{1}\def\and{\stepcounter{@auth}}% + \def\thanks##1{}\@author}% + \global\value{@inst}=\value{@auth}% + \global\value{auco}=\value{@auth}% + \setcounter{@auth}{1}% +{\lineskip .5em +\noindent\ignorespaces +\@author\vskip.35cm} + {\small\institutename} + \end{center}% + } + +% definition of the "\spnewtheorem" command. +% +% Usage: +% +% \spnewtheorem{env_nam}{caption}[within]{cap_font}{body_font} +% or \spnewtheorem{env_nam}[numbered_like]{caption}{cap_font}{body_font} +% or \spnewtheorem*{env_nam}{caption}{cap_font}{body_font} +% +% New is "cap_font" and "body_font". It stands for +% fontdefinition of the caption and the text itself. +% +% "\spnewtheorem*" gives a theorem without number. +% +% A defined spnewthoerem environment is used as described +% by Lamport. +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\def\@thmcountersep{} +\def\@thmcounterend{.} + +\def\spnewtheorem{\@ifstar{\@sthm}{\@Sthm}} + +% definition of \spnewtheorem with number + +\def\@spnthm#1#2{% + \@ifnextchar[{\@spxnthm{#1}{#2}}{\@spynthm{#1}{#2}}} +\def\@Sthm#1{\@ifnextchar[{\@spothm{#1}}{\@spnthm{#1}}} + +\def\@spxnthm#1#2[#3]#4#5{\expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}\@addtoreset{#1}{#3}% + \expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand + \csname the#3\endcsname \noexpand\@thmcountersep \@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@spynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}% + \expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#3}{#4}}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@spothm#1[#2]#3#4#5{% + \@ifundefined{c@#2}{\@latexerr{No theorem environment `#2' defined}\@eha}% + {\expandafter\@ifdefinable\csname #1\endcsname + {\newaliascnt{#1}{#2}% + \expandafter\xdef\csname #1name\endcsname{#3}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}% + \global\@namedef{end#1}{\@endtheorem}}}} + +\def\@spthm#1#2#3#4{\topsep 7\p@ \@plus2\p@ \@minus4\p@ +\refstepcounter{#1}% +\@ifnextchar[{\@spythm{#1}{#2}{#3}{#4}}{\@spxthm{#1}{#2}{#3}{#4}}} + +\def\@spxthm#1#2#3#4{\@spbegintheorem{#2}{\csname the#1\endcsname}{#3}{#4}% + \ignorespaces} + +\def\@spythm#1#2#3#4[#5]{\@spopargbegintheorem{#2}{\csname + the#1\endcsname}{#5}{#3}{#4}\ignorespaces} + +\def\@spbegintheorem#1#2#3#4{\trivlist + \item[\hskip\labelsep{#3#1\ #2\@thmcounterend}]#4} + +\def\@spopargbegintheorem#1#2#3#4#5{\trivlist + \item[\hskip\labelsep{#4#1\ #2}]{#4(#3)\@thmcounterend\ }#5} + +% definition of \spnewtheorem* without number + +\def\@sthm#1#2{\@Ynthm{#1}{#2}} + +\def\@Ynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname + {\global\@namedef{#1}{\@Thm{\csname #1name\endcsname}{#3}{#4}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@Thm#1#2#3{\topsep 7\p@ \@plus2\p@ \@minus4\p@ +\@ifnextchar[{\@Ythm{#1}{#2}{#3}}{\@Xthm{#1}{#2}{#3}}} + +\def\@Xthm#1#2#3{\@Begintheorem{#1}{#2}{#3}\ignorespaces} + +\def\@Ythm#1#2#3[#4]{\@Opargbegintheorem{#1} + {#4}{#2}{#3}\ignorespaces} + +\def\@Begintheorem#1#2#3{#3\trivlist + \item[\hskip\labelsep{#2#1\@thmcounterend}]} + +\def\@Opargbegintheorem#1#2#3#4{#4\trivlist + \item[\hskip\labelsep{#3#1}]{#3(#2)\@thmcounterend\ }} + +\if@envcntsect + \def\@thmcountersep{.} + \spnewtheorem{theorem}{Theorem}[section]{\bfseries}{\itshape} +\else + \spnewtheorem{theorem}{Theorem}{\bfseries}{\itshape} + \if@envcntreset + \@addtoreset{theorem}{section} + \else + \@addtoreset{theorem}{chapter} + \fi +\fi + +%definition of divers theorem environments +\spnewtheorem*{claim}{Claim}{\itshape}{\rmfamily} +\spnewtheorem*{proof}{Proof}{\itshape}{\rmfamily} +\if@envcntsame % alle Umgebungen wie Theorem. + \def\spn@wtheorem#1#2#3#4{\@spothm{#1}[theorem]{#2}{#3}{#4}} +\else % alle Umgebungen mit eigenem Zaehler + \if@envcntsect % mit section numeriert + \def\spn@wtheorem#1#2#3#4{\@spxnthm{#1}{#2}[section]{#3}{#4}} + \else % nicht mit section numeriert + \if@envcntreset + \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4} + \@addtoreset{#1}{section}} + \else + \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4} + \@addtoreset{#1}{chapter}}% + \fi + \fi +\fi +\spn@wtheorem{case}{Case}{\itshape}{\rmfamily} +\spn@wtheorem{conjecture}{Conjecture}{\itshape}{\rmfamily} +\spn@wtheorem{corollary}{Corollary}{\bfseries}{\itshape} +\spn@wtheorem{definition}{Definition}{\bfseries}{\itshape} +\spn@wtheorem{example}{Example}{\itshape}{\rmfamily} +\spn@wtheorem{exercise}{Exercise}{\itshape}{\rmfamily} +\spn@wtheorem{lemma}{Lemma}{\bfseries}{\itshape} +\spn@wtheorem{note}{Note}{\itshape}{\rmfamily} +\spn@wtheorem{problem}{Problem}{\itshape}{\rmfamily} +\spn@wtheorem{property}{Property}{\itshape}{\rmfamily} +\spn@wtheorem{proposition}{Proposition}{\bfseries}{\itshape} +\spn@wtheorem{question}{Question}{\itshape}{\rmfamily} +\spn@wtheorem{solution}{Solution}{\itshape}{\rmfamily} +\spn@wtheorem{remark}{Remark}{\itshape}{\rmfamily} + +\def\@takefromreset#1#2{% + \def\@tempa{#1}% + \let\@tempd\@elt + \def\@elt##1{% + \def\@tempb{##1}% + \ifx\@tempa\@tempb\else + \@addtoreset{##1}{#2}% + \fi}% + \expandafter\expandafter\let\expandafter\@tempc\csname cl@#2\endcsname + \expandafter\def\csname cl@#2\endcsname{}% + \@tempc + \let\@elt\@tempd} + +\def\theopargself{\def\@spopargbegintheorem##1##2##3##4##5{\trivlist + \item[\hskip\labelsep{##4##1\ ##2}]{##4##3\@thmcounterend\ }##5} + \def\@Opargbegintheorem##1##2##3##4{##4\trivlist + \item[\hskip\labelsep{##3##1}]{##3##2\@thmcounterend\ }} + } + +\renewenvironment{abstract}{% + \list{}{\advance\topsep by0.35cm\relax\small + \leftmargin=1cm + \labelwidth=\z@ + \listparindent=\z@ + \itemindent\listparindent + \rightmargin\leftmargin}\item[\hskip\labelsep + \bfseries\abstractname]} + {\endlist} + +\newdimen\headlineindent % dimension for space between +\headlineindent=1.166cm % number and text of headings. + +\def\ps@headings{\let\@mkboth\@gobbletwo + \let\@oddfoot\@empty\let\@evenfoot\@empty + \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \leftmark\hfil} + \def\@oddhead{\normalfont\small\hfil\rightmark\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\def\ps@titlepage{\let\@mkboth\@gobbletwo + \let\@oddfoot\@empty\let\@evenfoot\@empty + \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \hfil} + \def\@oddhead{\normalfont\small\hfil\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\if@runhead\ps@headings\else +\ps@empty\fi + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\endinput +%end of file llncs.cls diff --git a/main.tex b/main.tex index 83c4303..a7dc8ba 100644 --- a/main.tex +++ b/main.tex @@ -72,12 +72,12 @@ Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the a $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$ and allocates a set $S^*$ such that -% \begin{align*} - $ OPT + \begin{displaymath} + OPT \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+ \varepsilon - \simeq 12.98V(S^*) + \varepsilon.$ -% \end{align*} + \simeq 12.98V(S^*) + \varepsilon. + \end{displaymath} \end{theorem} The proof of the theorem, as well as our proposed mechanism, can be found in Appendix~\ref{sec:proofofmainthm}. In addition, we prove the following simple lower bound, proved in Appendix~\ref{proofoflowerbound}. diff --git a/paper.tex b/paper.tex index f1605c1..7abcf9a 100644 --- a/paper.tex +++ b/paper.tex @@ -1,31 +1,32 @@ -\documentclass[11pt,letterpaper]{article} -\usepackage[margin=1in]{geometry} -\usepackage[numbers]{natbib} +\documentclass[draft]{llncs} +\pagestyle{plain} +\usepackage[numbers, sectionbib]{natbib} \usepackage[utf8]{inputenc} \usepackage{amsmath,amsfonts} \usepackage{algorithm, algpseudocode} \usepackage{bbm,color,verbatim} -\usepackage{amsthm} \input{definitions} -\usepackage[pagebackref=true,breaklinks=true,colorlinks=true]{hyperref} +\usepackage[pagebackref=true,breaklinks=true,colorlinks=true,pagebackref=false]{hyperref} \title{Budget Feasible Mechanisms for Experimental Design} \author{ - Thibaut Horel\\École Normale Supérieure\\\texttt{thibaut.horel@normalesup.org} + Thibaut Horel\inst{1} \and - Stratis Ioannidis\\Technicolor\\\texttt{stratis.ioannidis@technicolor.com} + Stratis Ioannidis\inst{2} \and - S. Muthukrishnan\\Rutgers University--Microsoft Research\\\texttt{muthu@cs.rutgers.edu} + S. Muthukrishnan\inst{3} +} +\institute{École Normale Supérieure, \email{thibaut.horel@normalesup.org} + \and + Technicolor, \email{stratis.ioannidis@technicolor.com} + \and + Rutgers University, \email{muthu@cs.rutgers.edu} } - \begin{document} \maketitle -\thispagestyle{empty} \begin{abstract} \input{abstract} \end{abstract} -\clearpage -\setcounter{page}{1} \section{Introduction} \input{intro} @@ -39,8 +40,10 @@ \input{conclusion} \section*{Acknowledgments} \input{ack} -\bibliographystyle{abbrvnat} +\bibliographystyle{splncsnat} +\begin{footnotesize} \bibliography{notes} +\end{footnotesize} \appendix \input{appendix} \section{Extensions}\label{sec:ext} diff --git a/problem.tex b/problem.tex index c21135b..73647da 100644 --- a/problem.tex +++ b/problem.tex @@ -6,7 +6,7 @@ The theory of experimental design \cite{pukelsheim2006optimal,atkinson2007optimu Suppose that an experimenter \E\ wishes to conduct $k$ among $n$ possible experiments. Each experiment $i\in\mathcal{N}\defeq \{1,\ldots,n\}$ is associated with a set of parameters (or features) $x_i\in \reals^d$, normalized -so that $$b\leq \|x_i\|^2_2\leq 1,$$ for some $b>0$. Denote by $S\subseteq \mathcal{N}$, where $|S|=k$, the set of experiments selected; upon its execution, experiment $i\in S$ reveals an output variable (the ``measurement'') $y_i$, related to the experiment features $x_i$ through a linear function, \emph{i.e.}, +so that $b\leq \|x_i\|^2_2\leq 1,$ for some $b>0$. Denote by $S\subseteq \mathcal{N}$, where $|S|=k$, the set of experiments selected; upon its execution, experiment $i\in S$ reveals an output variable (the ``measurement'') $y_i$, related to the experiment features $x_i$ through a linear function, \emph{i.e.}, \begin{align}\label{model} \forall i\in\mathcal{N},\quad y_i = \T{\beta} x_i + \varepsilon_i \end{align} @@ -25,8 +25,11 @@ distribution on $\beta$, \emph{i.e.}, $\beta$ has a multivariate normal prior with zero mean and covariance $\sigma^2R^{-1}\in \reals^{d^2}$ (where $\sigma^2$ is the noise variance). Then, \E\ estimates $\beta$ through \emph{maximum a posteriori estimation}: \emph{i.e.}, finding the parameter which maximizes the posterior distribution of $\beta$ given the observations $y_S$. Under the linearity assumption \eqref{model} and the Gaussian prior on $\beta$, maximum a posteriori estimation leads to the following maximization \cite{hastie}: \begin{align} - \hat{\beta} = \argmax_{\beta\in\reals^d} \prob(\beta\mid y_S) =\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - \T{\beta}x_i)^2 - + \T{\beta}R\beta\big) = (R+\T{X_S}X_S)^{-1}X_S^Ty_S \label{ridge} + \begin{split} + \hat{\beta} = \argmax_{\beta\in\reals^d} \prob(\beta\mid y_S) &=\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - \T{\beta}x_i)^2 + + \T{\beta}R\beta\big)\\ + & = (R+\T{X_S}X_S)^{-1}X_S^Ty_S \label{ridge} +\end{split} \end{align} where the last equality is obtained by setting $\nabla_{\beta}\prob(\beta\mid y_S)$ to zero and solving the resulting linear system; in \eqref{ridge}, $X_S\defeq[x_i]_{i\in S}\in \reals^{|S|\times d}$ is the matrix of experiment features and $y_S\defeq[y_i]_{i\in S}\in\reals^{|S|}$ are the observed measurements. diff --git a/related.tex b/related.tex index 4b7e740..8cca712 100644 --- a/related.tex +++ b/related.tex @@ -36,7 +36,7 @@ establish that it can be incorporated in the framework of \paragraph{Beyond Submodular Objectives} Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists a truthful, $O(\log^3 n)$-approximate mechanism -\cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization +\cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-appro\-xi\-mate mechanism for subadditive maximization \cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations) Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}. diff --git a/splncs.bst b/splncs.bst new file mode 100644 index 0000000..fe8a22a --- /dev/null +++ b/splncs.bst @@ -0,0 +1,1098 @@ +% BibTeX bibliography style `splncs' + +% An attempt to match the bibliography style required for use with +% numbered references in Springer Verlag's "Lecture Notes in Computer +% Science" series. (See Springer's documentation for llncs.sty for +% more details of the suggested reference format.) Note that this +% file will not work for author-year style citations. + +% Use \documentclass{llncs} and \bibliographystyle{splncs}, and cite +% a reference with (e.g.) \cite{smith77} to get a "[1]" in the text. + +% Copyright (C) 1999 Jason Noble. +% Last updated: Friday 07 March 2006, 08:04:42 Frank Holzwarth, Springer +% +% Based on the BibTeX standard bibliography style `unsrt' + +ENTRY + { address + author + booktitle + chapter + edition + editor + howpublished + institution + journal + key + month + note + number + organization + pages + publisher + school + series + title + type + volume + year + } + {} + { label } + +INTEGERS { output.state before.all mid.sentence after.sentence + after.block after.authors between.elements} + +FUNCTION {init.state.consts} +{ #0 'before.all := + #1 'mid.sentence := + #2 'after.sentence := + #3 'after.block := + #4 'after.authors := + #5 'between.elements := +} + +STRINGS { s t } + +FUNCTION {output.nonnull} +{ 's := + output.state mid.sentence = + { " " * write$ } + { output.state after.block = + { add.period$ write$ + newline$ + "\newblock " write$ + } + { + output.state after.authors = + { ": " * write$ + newline$ + "\newblock " write$ + } + { output.state between.elements = + { ", " * write$ } + { output.state before.all = + 'write$ + { add.period$ " " * write$ } + if$ + } + if$ + } + if$ + } + if$ + mid.sentence 'output.state := + } + if$ + s +} + +FUNCTION {output} +{ duplicate$ empty$ + 'pop$ + 'output.nonnull + if$ +} + +FUNCTION {output.check} +{ 't := + duplicate$ empty$ + { pop$ "empty " t * " in " * cite$ * warning$ } + 'output.nonnull + if$ +} + +FUNCTION {output.bibitem} +{ newline$ + "\bibitem{" write$ + cite$ write$ + "}" write$ + newline$ + "" + before.all 'output.state := +} + +FUNCTION {fin.entry} +{ write$ + newline$ +} + +FUNCTION {new.block} +{ output.state before.all = + 'skip$ + { after.block 'output.state := } + if$ +} + +FUNCTION {stupid.colon} +{ after.authors 'output.state := } + +FUNCTION {insert.comma} +{ output.state before.all = + 'skip$ + { between.elements 'output.state := } + if$ +} + +FUNCTION {new.sentence} +{ output.state after.block = + 'skip$ + { output.state before.all = + 'skip$ + { after.sentence 'output.state := } + if$ + } + if$ +} + +FUNCTION {not} +{ { #0 } + { #1 } + if$ +} + +FUNCTION {and} +{ 'skip$ + { pop$ #0 } + if$ +} + +FUNCTION {or} +{ { pop$ #1 } + 'skip$ + if$ +} + +FUNCTION {new.block.checka} +{ empty$ + 'skip$ + 'new.block + if$ +} + +FUNCTION {new.block.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.block + if$ +} + +FUNCTION {new.sentence.checka} +{ empty$ + 'skip$ + 'new.sentence + if$ +} + +FUNCTION {new.sentence.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.sentence + if$ +} + +FUNCTION {field.or.null} +{ duplicate$ empty$ + { pop$ "" } + 'skip$ + if$ +} + +FUNCTION {emphasize} +{ duplicate$ empty$ + { pop$ "" } + { "" swap$ * "" * } + if$ +} + +FUNCTION {bold} +{ duplicate$ empty$ + { pop$ "" } + { "\textbf{" swap$ * "}" * } + if$ +} + +FUNCTION {parens} +{ duplicate$ empty$ + { pop$ "" } + { "(" swap$ * ")" * } + if$ +} + +INTEGERS { nameptr namesleft numnames } + +FUNCTION {format.springer.names} +{ 's := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr "{vv~}{ll}{, jj}{, f{.}.}" format.name$ 't := + nameptr #1 > + { namesleft #1 > + { ", " * t * } + { numnames #1 > + { ", " * } + 'skip$ + if$ + t "others" = + { " et~al." * } + { "" * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {format.names} +{ 's := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr "{vv~}{ll}{, jj}{, f.}" format.name$ 't := + nameptr #1 > + { namesleft #1 > + { ", " * t * } + { numnames #2 > + { "," * } + 'skip$ + if$ + t "others" = + { " et~al." * } + { " \& " * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {format.authors} +{ author empty$ + { "" } + { author format.springer.names } + if$ +} + +FUNCTION {format.editors} +{ editor empty$ + { "" } + { editor format.springer.names + editor num.names$ #1 > + { ", eds." * } + { ", ed." * } + if$ + } + if$ +} + +FUNCTION {format.title} +{ title empty$ + { "" } + { title "t" change.case$ } + if$ +} + +FUNCTION {n.dashify} +{ 't := + "" + { t empty$ not } + { t #1 #1 substring$ "-" = + { t #1 #2 substring$ "--" = not + { "--" * + t #2 global.max$ substring$ 't := + } + { { t #1 #1 substring$ "-" = } + { "-" * + t #2 global.max$ substring$ 't := + } + while$ + } + if$ + } + { t #1 #1 substring$ * + t #2 global.max$ substring$ 't := + } + if$ + } + while$ +} + +FUNCTION {format.date} +{ year empty$ + { month empty$ + { "" } + { "there's a month but no year in " cite$ * warning$ + month + } + if$ + } + { month empty$ + 'year + { month " " * year * } + if$ + } + if$ +} + +FUNCTION {format.btitle} +{ title emphasize +} + +FUNCTION {tie.or.space.connect} +{ duplicate$ text.length$ #3 < + { "~" } + { " " } + if$ + swap$ * * +} + +FUNCTION {either.or.check} +{ empty$ + 'pop$ + { "can't use both " swap$ * " fields in " * cite$ * warning$ } + if$ +} + +FUNCTION {format.bvolume} +{ volume empty$ + { "" } + { "Volume" volume tie.or.space.connect + series empty$ + 'skip$ + { " of " * series emphasize * } + if$ + add.period$ + "volume and number" number either.or.check + } + if$ +} + +FUNCTION {format.number.series} +{ volume empty$ + { number empty$ + { series field.or.null } + { output.state mid.sentence = + { "number" } + { "Number" } + if$ + number tie.or.space.connect + series empty$ + { "there's a number but no series in " cite$ * warning$ } + { " in " * series * } + if$ + } + if$ + } + { "" } + if$ +} + +FUNCTION {format.edition} +{ edition empty$ + { "" } + { output.state mid.sentence = + { edition "l" change.case$ " edn." * } + { edition "t" change.case$ " edn." * } + if$ + } + if$ +} + +INTEGERS { multiresult } + +FUNCTION {multi.page.check} +{ 't := + #0 'multiresult := + { multiresult not + t empty$ not + and + } + { t #1 #1 substring$ + duplicate$ "-" = + swap$ duplicate$ "," = + swap$ "+" = + or or + { #1 'multiresult := } + { t #2 global.max$ substring$ 't := } + if$ + } + while$ + multiresult +} + +FUNCTION {format.pages} +{ pages empty$ + { "" } + { pages multi.page.check + { "" pages n.dashify tie.or.space.connect } + { "" pages tie.or.space.connect } + if$ + } + if$ +} + +FUNCTION {format.vol} +{ volume bold +} + +FUNCTION {format.vol.num} +{ volume bold +number empty$ +{ } +{ number "(" swap$ * * ")" * } +if$ +} + +FUNCTION {pre.format.pages} +{ pages empty$ + 'skip$ + { duplicate$ empty$ + { pop$ format.pages } + { " " * pages n.dashify * } + if$ + } + if$ +} + +FUNCTION {format.chapter.pages} +{ chapter empty$ + 'format.pages + { type empty$ + { "chapter" } + { type "l" change.case$ } + if$ + chapter tie.or.space.connect + pages empty$ + 'skip$ + { " " * format.pages * } + if$ + } + if$ +} + +FUNCTION {format.in.ed.booktitle} +{ booktitle empty$ + { "" } + { editor empty$ + { "In: " booktitle emphasize * } + { "In " format.editors * ": " * booktitle emphasize * } + if$ + } + if$ +} + +FUNCTION {empty.misc.check} +{ author empty$ title empty$ howpublished empty$ + month empty$ year empty$ note empty$ + and and and and and + { "all relevant fields are empty in " cite$ * warning$ } + 'skip$ + if$ +} + +FUNCTION {format.thesis.type} +{ type empty$ + 'skip$ + { pop$ + type "t" change.case$ + } + if$ +} + +FUNCTION {format.tr.number} +{ type empty$ + { "Technical Report" } + 'type + if$ + number empty$ + { "t" change.case$ } + { number tie.or.space.connect } + if$ +} + +FUNCTION {format.article.crossref} +{ key empty$ + { journal empty$ + { "need key or journal for " cite$ * " to crossref " * crossref * + warning$ + "" + } + { "In {\em " journal * "\/}" * } + if$ + } + { "In " key * } + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {format.crossref.editor} +{ editor #1 "{vv~}{ll}" format.name$ + editor num.names$ duplicate$ + #2 > + { pop$ " et~al." * } + { #2 < + 'skip$ + { editor #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" = + { " et~al." * } + { " and " * editor #2 "{vv~}{ll}" format.name$ * } + if$ + } + if$ + } + if$ +} + +FUNCTION {format.book.crossref} +{ volume empty$ + { "empty volume in " cite$ * "'s crossref of " * crossref * warning$ + "In " + } + { "Volume" volume tie.or.space.connect + " of " * + } + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {format.incoll.inproc.crossref} +{ editor empty$ + editor field.or.null author field.or.null = + or + { key empty$ + { booktitle empty$ + { "need editor, key, or booktitle for " cite$ * " to crossref " * + crossref * warning$ + "" + } + { "" } + if$ + } + { "" } + if$ + } + { "" } + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {and.the.note} +{ note output + note empty$ + 'skip$ + { add.period$ } + if$ +} + +FUNCTION {article} +{ output.bibitem + format.authors "author" output.check + stupid.colon + format.title "title" output.check + new.block + crossref missing$ + { journal emphasize "journal" output.check + format.vol.num output + format.date parens output + format.pages output + } + { format.article.crossref output.nonnull + format.pages output + } + if$ + and.the.note + fin.entry +} + +FUNCTION {book} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + stupid.colon + format.btitle "title" output.check + new.sentence + crossref missing$ + { format.edition output + format.bvolume output + new.block + format.number.series output + new.sentence + publisher "publisher" output.check + address empty$ + 'skip$ + { insert.comma } + if$ + address output + format.date parens output + } + { format.book.crossref output.nonnull + } + if$ + and.the.note + fin.entry +} + +FUNCTION {booklet} +{ output.bibitem + format.authors output + stupid.colon + format.title "title" output.check + howpublished address new.block.checkb + howpublished output + address empty$ + 'skip$ + { insert.comma } + if$ + address output + format.date parens output + and.the.note + fin.entry +} + +FUNCTION {inbook} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + stupid.colon + crossref missing$ + { chapter output + new.block + format.number.series output + new.sentence + "In:" output + format.btitle "title" output.check + new.sentence + format.edition output + format.bvolume output + publisher "publisher" output.check + address empty$ + 'skip$ + { insert.comma } + if$ + address output + format.date parens output + } + { chapter output + new.block + format.incoll.inproc.crossref output.nonnull + } + if$ + format.pages output + and.the.note + fin.entry +} + +FUNCTION {incollection} +{ output.bibitem + format.authors "author" output.check + stupid.colon + format.title "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + new.sentence + format.bvolume output + format.number.series output + new.block + format.edition output + publisher "publisher" output.check + address empty$ + 'skip$ + { insert.comma } + if$ + address output + format.date parens output + format.pages output + } + { format.incoll.inproc.crossref output.nonnull + format.chapter.pages output + } + if$ + and.the.note + fin.entry +} + +FUNCTION {inproceedings} +{ output.bibitem + format.authors "author" output.check + stupid.colon + format.title "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + new.sentence + format.bvolume output + format.number.series output + address empty$ + { organization publisher new.sentence.checkb + organization empty$ + 'skip$ + { insert.comma } + if$ + organization output + publisher empty$ + 'skip$ + { insert.comma } + if$ + publisher output + format.date parens output + } + { insert.comma + address output.nonnull + organization empty$ + 'skip$ + { insert.comma } + if$ + organization output + publisher empty$ + 'skip$ + { insert.comma } + if$ + publisher output + format.date parens output + } + if$ + } + { format.incoll.inproc.crossref output.nonnull + } + if$ + format.pages output + and.the.note + fin.entry +} + +FUNCTION {conference} { inproceedings } + +FUNCTION {manual} +{ output.bibitem + author empty$ + { organization empty$ + 'skip$ + { organization output.nonnull + address output + } + if$ + } + { format.authors output.nonnull } + if$ + stupid.colon + format.btitle "title" output.check + author empty$ + { organization empty$ + { address new.block.checka + address output + } + 'skip$ + if$ + } + { organization address new.block.checkb + organization output + address empty$ + 'skip$ + { insert.comma } + if$ + address output + } + if$ + new.sentence + format.edition output + format.date parens output + and.the.note + fin.entry +} + +FUNCTION {mastersthesis} +{ output.bibitem + format.authors "author" output.check + stupid.colon + format.title "title" output.check + new.block + "Master's thesis" format.thesis.type output.nonnull + school empty$ + 'skip$ + { insert.comma } + if$ + school "school" output.check + address empty$ + 'skip$ + { insert.comma } + if$ + address output + format.date parens output + and.the.note + fin.entry +} + +FUNCTION {misc} +{ output.bibitem + format.authors "author" output.check + stupid.colon + format.title "title" output.check + howpublished new.block.checka + howpublished output + format.date parens output + and.the.note + fin.entry + empty.misc.check +} + +FUNCTION {phdthesis} +{ output.bibitem + format.authors "author" output.check + stupid.colon + format.btitle "title" output.check + new.block + "PhD thesis" format.thesis.type output.nonnull + school empty$ + 'skip$ + { insert.comma } + if$ + school "school" output.check + address empty$ + 'skip$ + { insert.comma } + if$ + address output + format.date parens output + and.the.note + fin.entry +} + +FUNCTION {proceedings} +{ output.bibitem + editor empty$ + { organization empty$ + { "" } + { organization output + stupid.colon } + if$ + } + { format.editors output.nonnull + stupid.colon + } + if$ + format.btitle "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + new.sentence + format.bvolume output + format.number.series output + address empty$ + { organization publisher new.sentence.checkb + organization empty$ + 'skip$ + { insert.comma } + if$ + organization output + publisher empty$ + 'skip$ + { insert.comma } + if$ + publisher output + format.date parens output + } + { insert.comma + address output.nonnull + organization empty$ + 'skip$ + { insert.comma } + if$ + organization output + publisher empty$ + 'skip$ + { insert.comma } + if$ + publisher output + format.date parens output + } + if$ + } + { format.incoll.inproc.crossref output.nonnull + } + if$ + and.the.note + fin.entry +} + +FUNCTION {techreport} +{ output.bibitem + format.authors "author" output.check + stupid.colon + format.title "title" output.check + new.block + format.tr.number output.nonnull + institution empty$ + 'skip$ + { insert.comma } + if$ + institution "institution" output.check + address empty$ + 'skip$ + { insert.comma } + if$ + address output + format.date parens output + and.the.note + fin.entry +} + +FUNCTION {unpublished} +{ output.bibitem + format.authors "author" output.check + stupid.colon + format.title "title" output.check + new.block + note "note" output.check + format.date parens output + fin.entry +} + +FUNCTION {default.type} { misc } + +MACRO {jan} {"January"} + +MACRO {feb} {"February"} + +MACRO {mar} {"March"} + +MACRO {apr} {"April"} + +MACRO {may} {"May"} + +MACRO {jun} {"June"} + +MACRO {jul} {"July"} + +MACRO {aug} {"August"} + +MACRO {sep} {"September"} + +MACRO {oct} {"October"} + +MACRO {nov} {"November"} + +MACRO {dec} {"December"} + +MACRO {acmcs} {"ACM Computing Surveys"} + +MACRO {acta} {"Acta Informatica"} + +MACRO {cacm} {"Communications of the ACM"} + +MACRO {ibmjrd} {"IBM Journal of Research and Development"} + +MACRO {ibmsj} {"IBM Systems Journal"} + +MACRO {ieeese} {"IEEE Transactions on Software Engineering"} + +MACRO {ieeetc} {"IEEE Transactions on Computers"} + +MACRO {ieeetcad} + {"IEEE Transactions on Computer-Aided Design of Integrated Circuits"} + +MACRO {ipl} {"Information Processing Letters"} + +MACRO {jacm} {"Journal of the ACM"} + +MACRO {jcss} {"Journal of Computer and System Sciences"} + +MACRO {scp} {"Science of Computer Programming"} + +MACRO {sicomp} {"SIAM Journal on Computing"} + +MACRO {tocs} {"ACM Transactions on Computer Systems"} + +MACRO {tods} {"ACM Transactions on Database Systems"} + +MACRO {tog} {"ACM Transactions on Graphics"} + +MACRO {toms} {"ACM Transactions on Mathematical Software"} + +MACRO {toois} {"ACM Transactions on Office Information Systems"} + +MACRO {toplas} {"ACM Transactions on Programming Languages and Systems"} + +MACRO {tcs} {"Theoretical Computer Science"} + +READ + +STRINGS { longest.label } + +INTEGERS { number.label longest.label.width } + +FUNCTION {initialize.longest.label} +{ "" 'longest.label := + #1 'number.label := + #0 'longest.label.width := +} + +FUNCTION {longest.label.pass} +{ number.label int.to.str$ 'label := + number.label #1 + 'number.label := + label width$ longest.label.width > + { label 'longest.label := + label width$ 'longest.label.width := + } + 'skip$ + if$ +} + +EXECUTE {initialize.longest.label} + +ITERATE {longest.label.pass} + +FUNCTION {begin.bib} +{ preamble$ empty$ + 'skip$ + { preamble$ write$ newline$ } + if$ + "\begin{thebibliography}{" longest.label * "}" * write$ newline$ +} + +EXECUTE {begin.bib} + +EXECUTE {init.state.consts} + +ITERATE {call.type$} + +FUNCTION {end.bib} +{ newline$ + "\end{thebibliography}" write$ newline$ +} + +EXECUTE {end.bib} + + + diff --git a/splncsnat.bst b/splncsnat.bst new file mode 100644 index 0000000..f808603 --- /dev/null +++ b/splncsnat.bst @@ -0,0 +1,1508 @@ +%% natbib-compatible BibTeX bibliography style `splncsnat' +%% +%% BibTeX bibliography style for use with numbered references in +%% Springer Verlag's "Lecture Notes in Computer Science" series. +%% (See Springer's documentation for llncs.cls for +%% more details of the suggested reference format.) +%% +%% Use +%% +%% \documentclass{llncs} +%% \usepackage[numbers]{natbib} +%% \bibliographystyle{splncsnat} +%% +%% and cite references with (e.g.) +%% +%% \cite{smith77} % to get a "[1]" in the text +%% \citep{smith77} % to get a "[1]" in the text +%% \citet{smith77} % to get a "Smith [1]" in the text +%% \citeauthor{smith77} % to get a "Smith" in the text +%% +%% The changes below are inspired by similar changes made to +%% splncs03.bst by Maurizio "Titto" Patrignani of +%% Dipartimento di Informatica e Automazione Universita' Roma Tre. +%% Unfortunately, splncs03.bst was not compatible with natbib (because it +%% was not built with author-year capability). +%% +%% ================================================================================================ +%% MANUAL CHANGES +%% (with respect to splncsnat-unpatched.bst produced from +%% splncsnat-unpatched.dbj): +%% [ search for ++++ to find the changes ] +%% - Emptied \urlprefix by default +%% - Added a new.sentence command to separate with a dot booktitle and series in the inproceedings +%% - Commented all new.block commands before notes (to separate them with a comma) +%% ================================================================================================ +%% +%% This is derived from `splncsnat-unpatched.bst', +%% generated with the docstrip utility. +%% +%% The original source files for splncsnat-unpatched.bst were: +%% +%% merlin.mbs (with options: `ay,nat,vonx,nm-rvvc,ed-rev,yr-par,aymth,note-yr,jttl-rm,volp-com,numser,ser-vol,jnm-x,btit-rm,bt-rm,edparxc,au-col,in-col,fin-bare,pp,ed,abr,mth-bare,xedn,jabr,and-com,and-com-ed,xand,url,url-nt,em-x,nfss,') +%% ---------------------------------------- +%% *** natbib-compatible .bst file for Springer LNCS *** +%% +%% Copyright 1994-2007 Patrick W Daly + % =============================================================== + % IMPORTANT NOTICE: + % This bibliographic style (bst) file has been generated from one or + % more master bibliographic style (mbs) files, listed above. + % + % This generated file can be redistributed and/or modified under the terms + % of the LaTeX Project Public License Distributed from CTAN + % archives in directory macros/latex/base/lppl.txt; either + % version 1 of the License, or any later version. + % =============================================================== + % Name and version information of the main mbs file: + % \ProvidesFile{merlin.mbs}[2007/04/24 4.20 (PWD, AO, DPC)] + % For use with BibTeX version 0.99a or later + %------------------------------------------------------------------- + % This bibliography style file is intended for texts in ENGLISH + % This is an author-year citation style bibliography. As such, it is + % non-standard LaTeX, and requires a special package file to function properly. + % Such a package is natbib.sty by Patrick W. Daly + % The form of the \bibitem entries is + % \bibitem[Jones et al.(1990)]{key}... + % \bibitem[Jones et al.(1990)Jones, Baker, and Smith]{key}... + % The essential feature is that the label (the part in brackets) consists + % of the author names, as they should appear in the citation, with the year + % in parentheses following. There must be no space before the opening + % parenthesis! + % With natbib v5.3, a full list of authors may also follow the year. + % In natbib.sty, it is possible to define the type of enclosures that is + % really wanted (brackets or parentheses), but in either case, there must + % be parentheses in the label. + % The \cite command functions as follows: + % \citet{key} ==>> Jones et al. (1990) + % \citet*{key} ==>> Jones, Baker, and Smith (1990) + % \citep{key} ==>> (Jones et al., 1990) + % \citep*{key} ==>> (Jones, Baker, and Smith, 1990) + % \citep[chap. 2]{key} ==>> (Jones et al., 1990, chap. 2) + % \citep[e.g.][]{key} ==>> (e.g. Jones et al., 1990) + % \citep[e.g.][p. 32]{key} ==>> (e.g. Jones et al., p. 32) + % \citeauthor{key} ==>> Jones et al. + % \citeauthor*{key} ==>> Jones, Baker, and Smith + % \citeyear{key} ==>> 1990 + %--------------------------------------------------------------------- + +ENTRY + { address + author + booktitle + chapter + edition + editor + eid + howpublished + institution + journal + key + month + note + number + organization + pages + publisher + school + series + title + type + url + volume + year + } + {} + { label extra.label sort.label short.list } +INTEGERS { output.state before.all mid.sentence after.sentence after.block } +FUNCTION {init.state.consts} +{ #0 'before.all := + #1 'mid.sentence := + #2 'after.sentence := + #3 'after.block := +} +STRINGS { s t} +FUNCTION {output.nonnull} +{ 's := + output.state mid.sentence = + { ", " * write$ } + { output.state after.block = + { add.period$ write$ + newline$ + "\newblock " write$ + } + { output.state before.all = + 'write$ + { add.period$ " " * write$ } + if$ + } + if$ + mid.sentence 'output.state := + } + if$ + s +} +FUNCTION {output} +{ duplicate$ empty$ + 'pop$ + 'output.nonnull + if$ +} +FUNCTION {output.check} +{ 't := + duplicate$ empty$ + { pop$ "empty " t * " in " * cite$ * warning$ } + 'output.nonnull + if$ +} +FUNCTION {fin.entry} +{ duplicate$ empty$ + 'pop$ + 'write$ + if$ + newline$ +} + +FUNCTION {new.block} +{ output.state before.all = + 'skip$ + { after.block 'output.state := } + if$ +} +FUNCTION {new.sentence} +{ output.state after.block = + 'skip$ + { output.state before.all = + 'skip$ + { after.sentence 'output.state := } + if$ + } + if$ +} +FUNCTION {add.blank} +{ " " * before.all 'output.state := +} + +FUNCTION {add.colon} +{ duplicate$ empty$ + 'skip$ + { ":" * add.blank } + if$ +} + +FUNCTION {date.block} +{ + new.block +} + +FUNCTION {not} +{ { #0 } + { #1 } + if$ +} +FUNCTION {and} +{ 'skip$ + { pop$ #0 } + if$ +} +FUNCTION {or} +{ { pop$ #1 } + 'skip$ + if$ +} +STRINGS {z} +FUNCTION {remove.dots} +{ 'z := + "" + { z empty$ not } + { z #1 #1 substring$ + z #2 global.max$ substring$ 'z := + duplicate$ "." = 'pop$ + { * } + if$ + } + while$ +} +FUNCTION {new.block.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.block + if$ +} +FUNCTION {field.or.null} +{ duplicate$ empty$ + { pop$ "" } + 'skip$ + if$ +} +FUNCTION {emphasize} +{ skip$ } +FUNCTION {tie.or.space.prefix} +{ duplicate$ text.length$ #3 < + { "~" } + { " " } + if$ + swap$ +} + +FUNCTION {capitalize} +{ "u" change.case$ "t" change.case$ } + +FUNCTION {space.word} +{ " " swap$ * " " * } + % Here are the language-specific definitions for explicit words. + % Each function has a name bbl.xxx where xxx is the English word. + % The language selected here is ENGLISH +FUNCTION {bbl.and} +{ "and"} + +FUNCTION {bbl.etal} +{ "et~al." } + +FUNCTION {bbl.editors} +{ "eds." } + +FUNCTION {bbl.editor} +{ "ed." } + +FUNCTION {bbl.edby} +{ "edited by" } + +FUNCTION {bbl.edition} +{ "edn." } + +FUNCTION {bbl.volume} +{ "vol." } + +FUNCTION {bbl.of} +{ "of" } + +FUNCTION {bbl.number} +{ "no." } + +FUNCTION {bbl.nr} +{ "no." } + +FUNCTION {bbl.in} +{ "in" } + +FUNCTION {bbl.pages} +{ "pp." } + +FUNCTION {bbl.page} +{ "p." } + +FUNCTION {bbl.chapter} +{ "chap." } + +FUNCTION {bbl.techrep} +{ "Tech. Rep." } + +FUNCTION {bbl.mthesis} +{ "Master's thesis" } + +FUNCTION {bbl.phdthesis} +{ "Ph.D. thesis" } + +MACRO {jan} {"Jan."} + +MACRO {feb} {"Feb."} + +MACRO {mar} {"Mar."} + +MACRO {apr} {"Apr."} + +MACRO {may} {"May"} + +MACRO {jun} {"Jun."} + +MACRO {jul} {"Jul."} + +MACRO {aug} {"Aug."} + +MACRO {sep} {"Sep."} + +MACRO {oct} {"Oct."} + +MACRO {nov} {"Nov."} + +MACRO {dec} {"Dec."} + +MACRO {acmcs} {"ACM Comput. Surv."} + +MACRO {acta} {"Acta Inf."} + +MACRO {cacm} {"Commun. ACM"} + +MACRO {ibmjrd} {"IBM J. Res. Dev."} + +MACRO {ibmsj} {"IBM Syst.~J."} + +MACRO {ieeese} {"IEEE Trans. Software Eng."} + +MACRO {ieeetc} {"IEEE Trans. Comput."} + +MACRO {ieeetcad} + {"IEEE Trans. Comput. Aid. Des."} + +MACRO {ipl} {"Inf. Process. Lett."} + +MACRO {jacm} {"J.~ACM"} + +MACRO {jcss} {"J.~Comput. Syst. Sci."} + +MACRO {scp} {"Sci. Comput. Program."} + +MACRO {sicomp} {"SIAM J. Comput."} + +MACRO {tocs} {"ACM Trans. Comput. Syst."} + +MACRO {tods} {"ACM Trans. Database Syst."} + +MACRO {tog} {"ACM Trans. Graphic."} + +MACRO {toms} {"ACM Trans. Math. Software"} + +MACRO {toois} {"ACM Trans. Office Inf. Syst."} + +MACRO {toplas} {"ACM Trans. Progr. Lang. Syst."} + +MACRO {tcs} {"Theor. Comput. Sci."} + +FUNCTION {bibinfo.check} +{ swap$ + duplicate$ missing$ + { + pop$ pop$ + "" + } + { duplicate$ empty$ + { + swap$ pop$ + } + { swap$ + pop$ + } + if$ + } + if$ +} +FUNCTION {bibinfo.warn} +{ swap$ + duplicate$ missing$ + { + swap$ "missing " swap$ * " in " * cite$ * warning$ pop$ + "" + } + { duplicate$ empty$ + { + swap$ "empty " swap$ * " in " * cite$ * warning$ + } + { swap$ + pop$ + } + if$ + } + if$ +} +INTEGERS { nameptr namesleft numnames } + + +STRINGS { bibinfo} + +FUNCTION {format.names} +{ 'bibinfo := + duplicate$ empty$ 'skip$ { + 's := + "" 't := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr + "{vv~}{ll}{, jj}{, f{.}.}" + format.name$ + bibinfo bibinfo.check + 't := + nameptr #1 > + { + namesleft #1 > + { ", " * t * } + { + s nameptr "{ll}" format.name$ duplicate$ "others" = + { 't := } + { pop$ } + if$ + "," * + t "others" = + { + " " * bbl.etal * + } + { " " * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ + } if$ +} +FUNCTION {format.names.ed} +{ + format.names +} +FUNCTION {format.key} +{ empty$ + { key field.or.null } + { "" } + if$ +} + +FUNCTION {format.authors} +{ author "author" format.names +} +FUNCTION {get.bbl.editor} +{ editor num.names$ #1 > 'bbl.editors 'bbl.editor if$ } + +FUNCTION {format.editors} +{ editor "editor" format.names duplicate$ empty$ 'skip$ + { + " " * + get.bbl.editor + "(" swap$ * ")" * + * + } + if$ +} +FUNCTION {format.note} +{ + url empty$ + 'skip$ + { "\urlprefix\url{" url * "}" * output } + if$ + note empty$ + { "" } + { note #1 #1 substring$ + duplicate$ "{" = + 'skip$ + { output.state mid.sentence = + { "l" } + { "u" } + if$ + change.case$ + } + if$ + note #2 global.max$ substring$ * "note" bibinfo.check + } + if$ +} + +FUNCTION {format.title} +{ title + duplicate$ empty$ 'skip$ + { "t" change.case$ } + if$ + "title" bibinfo.check +} +FUNCTION {format.full.names} +{'s := + "" 't := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr + "{vv~}{ll}" format.name$ + 't := + nameptr #1 > + { + namesleft #1 > + { ", " * t * } + { + s nameptr "{ll}" format.name$ duplicate$ "others" = + { 't := } + { pop$ } + if$ + t "others" = + { + " " * bbl.etal * + } + { + numnames #2 > + { "," * } + 'skip$ + if$ + bbl.and + space.word * t * + } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {author.editor.key.full} +{ author empty$ + { editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.full.names } + if$ + } + { author format.full.names } + if$ +} + +FUNCTION {author.key.full} +{ author empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { author format.full.names } + if$ +} + +FUNCTION {editor.key.full} +{ editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.full.names } + if$ +} + +FUNCTION {make.full.names} +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.key.full + { type$ "proceedings" = + 'editor.key.full + 'author.key.full + if$ + } + if$ +} + +FUNCTION {output.bibitem} +{ newline$ + "\bibitem[{" write$ + label write$ + ")" make.full.names duplicate$ short.list = + { pop$ } + { * } + if$ + "}]{" * write$ + cite$ write$ + "}" write$ + newline$ + "" + before.all 'output.state := +} + +FUNCTION {n.dashify} +{ + 't := + "" + { t empty$ not } + { t #1 #1 substring$ "-" = + { t #1 #2 substring$ "--" = not + { "--" * + t #2 global.max$ substring$ 't := + } + { { t #1 #1 substring$ "-" = } + { "-" * + t #2 global.max$ substring$ 't := + } + while$ + } + if$ + } + { t #1 #1 substring$ * + t #2 global.max$ substring$ 't := + } + if$ + } + while$ +} + +FUNCTION {word.in} +{ bbl.in capitalize + ":" * + " " * } + +FUNCTION {format.date} +{ year "year" bibinfo.check duplicate$ empty$ + { + "empty year in " cite$ * "; set to ????" * warning$ + pop$ "????" + } + 'skip$ + if$ + month "month" bibinfo.check duplicate$ empty$ + 'skip$ + { + " " * swap$ + } + if$ + * + remove.dots + extra.label * + before.all 'output.state := + " (" swap$ * ")" * +} +FUNCTION {format.btitle} +{ title "title" bibinfo.check + duplicate$ empty$ 'skip$ + { + } + if$ +} +FUNCTION {either.or.check} +{ empty$ + 'pop$ + { "can't use both " swap$ * " fields in " * cite$ * warning$ } + if$ +} +FUNCTION {format.bvolume} +{ volume empty$ + { "" } + { bbl.volume volume tie.or.space.prefix + "volume" bibinfo.check * * + series "series" bibinfo.check + duplicate$ empty$ 'pop$ + { emphasize ", " * swap$ * } + if$ + "volume and number" number either.or.check + } + if$ +} +FUNCTION {format.number.series} +{ volume empty$ + { number empty$ + { series field.or.null } + { output.state mid.sentence = + { bbl.number } + { bbl.number capitalize } + if$ + number tie.or.space.prefix "number" bibinfo.check * * + series empty$ + { "there's a number but no series in " cite$ * warning$ } + { bbl.in space.word * + series "series" bibinfo.check * + } + if$ + } + if$ + } + { "" } + if$ +} + +FUNCTION {format.edition} +{ edition duplicate$ empty$ 'skip$ + { + output.state mid.sentence = + { "l" } + { "t" } + if$ change.case$ + "edition" bibinfo.check + " " * bbl.edition * + } + if$ +} +INTEGERS { multiresult } +FUNCTION {multi.page.check} +{ 't := + #0 'multiresult := + { multiresult not + t empty$ not + and + } + { t #1 #1 substring$ + duplicate$ "-" = + swap$ duplicate$ "," = + swap$ "+" = + or or + { #1 'multiresult := } + { t #2 global.max$ substring$ 't := } + if$ + } + while$ + multiresult +} +FUNCTION {format.pages} +{ pages duplicate$ empty$ 'skip$ + { duplicate$ multi.page.check + { + bbl.pages swap$ + n.dashify + } + { + bbl.page swap$ + } + if$ + tie.or.space.prefix + "pages" bibinfo.check + * * + } + if$ +} +FUNCTION {format.journal.pages} +{ pages duplicate$ empty$ 'pop$ + { swap$ duplicate$ empty$ + { pop$ pop$ format.pages } + { + ", " * + swap$ + n.dashify + "pages" bibinfo.check + * + } + if$ + } + if$ +} +FUNCTION {format.journal.eid} +{ eid "eid" bibinfo.check + duplicate$ empty$ 'pop$ + { swap$ duplicate$ empty$ 'skip$ + { + ", " * + } + if$ + swap$ * + } + if$ +} +FUNCTION {format.vol.num.pages} +{ volume field.or.null + duplicate$ empty$ 'skip$ + { + "volume" bibinfo.check + } + if$ + number "number" bibinfo.check duplicate$ empty$ 'skip$ + { + swap$ duplicate$ empty$ + { "there's a number but no volume in " cite$ * warning$ } + 'skip$ + if$ + swap$ + "(" swap$ * ")" * + } + if$ * + eid empty$ + { format.journal.pages } + { format.journal.eid } + if$ +} + +FUNCTION {format.chapter.pages} +{ chapter empty$ + 'format.pages + { type empty$ + { bbl.chapter } + { type "l" change.case$ + "type" bibinfo.check + } + if$ + chapter tie.or.space.prefix + "chapter" bibinfo.check + * * + pages empty$ + 'skip$ + { ", " * format.pages * } + if$ + } + if$ +} + +FUNCTION {format.booktitle} +{ + booktitle "booktitle" bibinfo.check +} +FUNCTION {format.in.ed.booktitle} +{ format.booktitle duplicate$ empty$ 'skip$ + { + editor "editor" format.names.ed duplicate$ empty$ 'pop$ + { + " " * + get.bbl.editor + "(" swap$ * ") " * + * swap$ + * } + if$ + word.in swap$ * + } + if$ +} +FUNCTION {format.thesis.type} +{ type duplicate$ empty$ + 'pop$ + { swap$ pop$ + "t" change.case$ "type" bibinfo.check + } + if$ +} +FUNCTION {format.tr.number} +{ number "number" bibinfo.check + type duplicate$ empty$ + { pop$ bbl.techrep } + 'skip$ + if$ + "type" bibinfo.check + swap$ duplicate$ empty$ + { pop$ "t" change.case$ } + { tie.or.space.prefix * * } + if$ +} +FUNCTION {format.article.crossref} +{ + word.in + " \cite{" * crossref * "}" * +} +FUNCTION {format.book.crossref} +{ volume duplicate$ empty$ + { "empty volume in " cite$ * "'s crossref of " * crossref * warning$ + pop$ word.in + } + { bbl.volume + capitalize + swap$ tie.or.space.prefix "volume" bibinfo.check * * bbl.of space.word * + } + if$ + " \cite{" * crossref * "}" * +} +FUNCTION {format.incoll.inproc.crossref} +{ + word.in + " \cite{" * crossref * "}" * +} +FUNCTION {format.org.or.pub} +{ 't := + "" + address empty$ t empty$ and + 'skip$ + { + t empty$ + { address "address" bibinfo.check * + } + { t * + address empty$ + 'skip$ + { ", " * address "address" bibinfo.check * } + if$ + } + if$ + } + if$ +} +FUNCTION {format.publisher.address} +{ publisher "publisher" bibinfo.warn format.org.or.pub +} + +FUNCTION {format.organization.address} +{ organization "organization" bibinfo.check format.org.or.pub +} + +FUNCTION {article} +{ output.bibitem + format.authors "author" output.check + author format.key output + add.colon + new.block + format.title "title" output.check + new.block + crossref missing$ + { + journal + "journal" bibinfo.check + "journal" output.check + add.blank + format.vol.num.pages output + format.date "year" output.check + } + { format.article.crossref output.nonnull + format.pages output + } + if$ + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} +FUNCTION {book} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check + editor format.key output + add.colon + } + { format.authors output.nonnull + add.colon + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + new.block + format.btitle "title" output.check + crossref missing$ + { format.bvolume output + new.block + new.sentence + format.number.series output + format.publisher.address output + } + { + new.block + format.book.crossref output.nonnull + } + if$ + format.edition output + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} +FUNCTION {booklet} +{ output.bibitem + format.authors output + author format.key output + add.colon + new.block + format.title "title" output.check + new.block + howpublished "howpublished" bibinfo.check output + address "address" bibinfo.check output + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} + +FUNCTION {inbook} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check + editor format.key output + add.colon + } + { format.authors output.nonnull + add.colon + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + new.block + format.btitle "title" output.check + crossref missing$ + { + format.bvolume output + format.chapter.pages "chapter and pages" output.check + new.block + new.sentence + format.number.series output + format.publisher.address output + } + { + format.chapter.pages "chapter and pages" output.check + new.block + format.book.crossref output.nonnull + } + if$ + format.edition output + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} + +FUNCTION {incollection} +{ output.bibitem + format.authors "author" output.check + author format.key output + add.colon + new.block + format.title "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.bvolume output + format.chapter.pages output + new.sentence + format.number.series output + format.publisher.address output + format.edition output + format.date "year" output.check + } + { format.incoll.inproc.crossref output.nonnull + format.chapter.pages output + } + if$ + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} +FUNCTION {inproceedings} +{ output.bibitem + format.authors "author" output.check + author format.key output + add.colon + new.block + format.title "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + new.sentence % ++++ ADDED (to get period b/w booktitle and series) + format.bvolume output + format.pages output + new.sentence + format.number.series output + publisher empty$ + { format.organization.address output } + { organization "organization" bibinfo.check output + format.publisher.address output + } + if$ + format.date "year" output.check + } + { format.incoll.inproc.crossref output.nonnull + format.pages output + } + if$ + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} +FUNCTION {conference} { inproceedings } +FUNCTION {manual} +{ output.bibitem + format.authors output + author format.key output + add.colon + new.block + format.btitle "title" output.check + organization address new.block.checkb + organization "organization" bibinfo.check output + address "address" bibinfo.check output + format.edition output + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} + +FUNCTION {mastersthesis} +{ output.bibitem + format.authors "author" output.check + author format.key output + add.colon + new.block + format.btitle + "title" output.check + new.block + bbl.mthesis format.thesis.type output.nonnull + school "school" bibinfo.warn output + address "address" bibinfo.check output + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} + +FUNCTION {misc} +{ output.bibitem + format.authors output + author format.key output + add.colon + new.block + format.title output + new.block + howpublished "howpublished" bibinfo.check output + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} +FUNCTION {phdthesis} +{ output.bibitem + format.authors "author" output.check + author format.key output + add.colon + new.block + format.btitle + "title" output.check + new.block + bbl.phdthesis format.thesis.type output.nonnull + school "school" bibinfo.warn output + address "address" bibinfo.check output + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} + +FUNCTION {proceedings} +{ output.bibitem + format.editors output + editor format.key output + add.colon + new.block + format.btitle "title" output.check + format.bvolume output + new.sentence + format.number.series output + publisher empty$ + { format.organization.address output } + { organization "organization" bibinfo.check output + format.publisher.address output + } + if$ + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} + +FUNCTION {techreport} +{ output.bibitem + format.authors "author" output.check + author format.key output + add.colon + new.block + format.title + "title" output.check + new.block + format.tr.number output.nonnull + institution "institution" bibinfo.warn output + address "address" bibinfo.check output + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note output + fin.entry +} + +FUNCTION {unpublished} +{ output.bibitem + format.authors "author" output.check + author format.key output + add.colon + new.block + format.title "title" output.check + format.date "year" output.check + % new.block ++++ REMOVED (to get comma before note) + format.note "note" output.check + fin.entry +} + +FUNCTION {default.type} { misc } +READ +FUNCTION {sortify} +{ purify$ + "l" change.case$ +} +INTEGERS { len } +FUNCTION {chop.word} +{ 's := + 'len := + s #1 len substring$ = + { s len #1 + global.max$ substring$ } + 's + if$ +} +FUNCTION {format.lab.names} +{ 's := + "" 't := + s #1 "{vv~}{ll}" format.name$ + s num.names$ duplicate$ + #2 > + { pop$ + " " * bbl.etal * + } + { #2 < + 'skip$ + { s #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" = + { + " " * bbl.etal * + } + { bbl.and space.word * s #2 "{vv~}{ll}" format.name$ + * } + if$ + } + if$ + } + if$ +} + +FUNCTION {author.key.label} +{ author empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {author.editor.key.label} +{ author empty$ + { editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.lab.names } + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {editor.key.label} +{ editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.lab.names } + if$ +} + +FUNCTION {calc.short.authors} +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.key.label + { type$ "proceedings" = + 'editor.key.label + 'author.key.label + if$ + } + if$ + 'short.list := +} + +FUNCTION {calc.label} +{ calc.short.authors + short.list + "(" + * + year duplicate$ empty$ + { pop$ "????" } + 'skip$ + if$ + * + 'label := +} + +FUNCTION {sort.format.names} +{ 's := + #1 'nameptr := + "" + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr + "{ll{ }}{ ff{ }}{ jj{ }}" + format.name$ 't := + nameptr #1 > + { + " " * + namesleft #1 = t "others" = and + { "zzzzz" * } + { t sortify * } + if$ + } + { t sortify * } + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {sort.format.title} +{ 't := + "A " #2 + "An " #3 + "The " #4 t chop.word + chop.word + chop.word + sortify + #1 global.max$ substring$ +} +FUNCTION {author.sort} +{ author empty$ + { key empty$ + { "to sort, need author or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { author sort.format.names } + if$ +} +FUNCTION {author.editor.sort} +{ author empty$ + { editor empty$ + { key empty$ + { "to sort, need author, editor, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { editor sort.format.names } + if$ + } + { author sort.format.names } + if$ +} +FUNCTION {editor.sort} +{ editor empty$ + { key empty$ + { "to sort, need editor or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { editor sort.format.names } + if$ +} +FUNCTION {presort} +{ calc.label + label sortify + " " + * + type$ "book" = + type$ "inbook" = + or + 'author.editor.sort + { type$ "proceedings" = + 'editor.sort + 'author.sort + if$ + } + if$ + #1 entry.max$ substring$ + 'sort.label := + sort.label + * + " " + * + title field.or.null + sort.format.title + * + #1 entry.max$ substring$ + 'sort.key$ := +} + +ITERATE {presort} +SORT +STRINGS { last.label next.extra } +INTEGERS { last.extra.num number.label } +FUNCTION {initialize.extra.label.stuff} +{ #0 int.to.chr$ 'last.label := + "" 'next.extra := + #0 'last.extra.num := + #0 'number.label := +} +FUNCTION {forward.pass} +{ last.label label = + { last.extra.num #1 + 'last.extra.num := + last.extra.num int.to.chr$ 'extra.label := + } + { "a" chr.to.int$ 'last.extra.num := + "" 'extra.label := + label 'last.label := + } + if$ + number.label #1 + 'number.label := +} +FUNCTION {reverse.pass} +{ next.extra "b" = + { "a" 'extra.label := } + 'skip$ + if$ + extra.label 'next.extra := + extra.label + duplicate$ empty$ + 'skip$ + { "{\natexlab{" swap$ * "}}" * } + if$ + 'extra.label := + label extra.label * 'label := +} +EXECUTE {initialize.extra.label.stuff} +ITERATE {forward.pass} +REVERSE {reverse.pass} +FUNCTION {bib.sort.order} +{ sort.label + " " + * + year field.or.null sortify + * + " " + * + title field.or.null + sort.format.title + * + #1 entry.max$ substring$ + 'sort.key$ := +} +ITERATE {bib.sort.order} +SORT +FUNCTION {begin.bib} +{ preamble$ empty$ + 'skip$ + { preamble$ write$ newline$ } + if$ + "\begin{thebibliography}{" number.label int.to.str$ * "}" * + write$ newline$ + "\providecommand{\natexlab}[1]{#1}" + write$ newline$ + "\providecommand{\url}[1]{\texttt{#1}}" + write$ newline$ +% "\providecommand{\urlprefix}{URL }" ++++ EMPTIED by default + "\providecommand{\urlprefix}{}" + write$ newline$ +} +EXECUTE {begin.bib} +EXECUTE {init.state.consts} +ITERATE {call.type$} +FUNCTION {end.bib} +{ newline$ + "\end{thebibliography}" write$ newline$ +} +EXECUTE {end.bib} +%% End of customized bst file +%% +%% End of file `splncsnat.bst'. -- cgit v1.2.3-70-g09d2